binary min heap in Julia

min-heap.jl

module Heap

export peek, min_insert!, extract_min!, build_min_heap!, decrease_key!

macro parent(i)
    :($i>>1) # i/2
end

macro left(i)
    :($i<<1) # 2i
end

macro right(i)
    :($i<<1+1) # 2i+1
end

peek(H) = H[1]

function min_insert!(H, key)
    new_size = size(H, 1) + 1
    resize!(H, new_size)
    H[new_size] = key
    decrease_key!(H, new_size, key)
end

function decrease_key!(H, i, key)
    key > H[i] && error("New key > Current key")

    H[i] = key
    while i > 1 && H[@parent i] > H[i]
        H[i], H[@parent i] = H[@parent i], H[i]
        i = @parent i
    end
end

function extract_min!(H)
    size(H, 1) < 1 && error("Heap empty")

    min = H[1]
    H[1] = H[size(H, 1)]
    resize!(H, size(H, 1) - 1)
    min_heapify!(H, 1)
    return min
end

function min_heapify!(H, i)
    l = @left i
    r = @right i

    if l <= size(H, 1) && H[l] < H[i]
        smallest = l
    else
        smallest = i
    end

    if r <= size(H, 1) && H[r] < H[smallest]
        smallest = r
    end

    if smallest != i
        H[i], H[smallest] = H[smallest], H[i]
        min_heapify!(H, smallest)
    end
end

function build_min_heap!(A)
    for i = 1:(size(A, 1)>>1)
        min_heapify!(A, size(A, 1)>>1+1-i)
    end
    return A
end

end