In [1]:

    

type BinaryMaxHeap
    heap::Array{Int}
    ind::Int
    BinaryMaxHeap(m_max::Int) = new(Array(Int, m_max), 0)
end


    

In [2]:

    

function reshape_up!(bmh::BinaryMaxHeap)
    current_ind = bmh.ind
    while true
        par = current_ind >> 1
        if par == 0 || bmh.heap[current_ind] <= bmh.heap[par]
            break
        else
            bmh.heap[current_ind], bmh.heap[par] = bmh.heap[par], bmh.heap[current_ind]
        end
        current_ind = par
    end
end


    

    
Out[2]:





reshape_up! (generic function with 1 method)

In [3]:

    

function reshape_down!(bmh::BinaryMaxHeap)
    current_ind = 1
    while true
        c1, c2 = current_ind * 2, current_ind * 2 + 1
        if c1 > bmh.ind
            break
        elseif c2 > bmh.ind
            c = c1
        else
            c = bmh.heap[c1] < bmh.heap[c2] ? c2 : c1
        end
        if bmh.heap[current_ind] < bmh.heap[c]
            bmh.heap[c], bmh.heap[current_ind] = bmh.heap[current_ind], bmh.heap[c]
            current_ind = c
        else
            break
        end
    end
end


    

    
Out[3]:





reshape_down! (generic function with 1 method)

In [4]:

    

function push!(bmh::BinaryMaxHeap, priority::Int)
    bmh.ind += 1
    bmh.heap[bmh.ind] = priority
    reshape_up!(bmh)
end


    

    
Out[4]:





push! (generic function with 1 method)

In [5]:

    

function pop!(bmh::BinaryMaxHeap)
    ret_val = bmh.heap[1]
    bmh.heap[1] = bmh.heap[bmh.ind]
    bmh.ind -= 1
    reshape_down!(bmh)
    return ret_val
end


    

    
Out[5]:





pop! (generic function with 1 method)

In [6]:

    

function top(bmh::BinaryMaxHeap)
    if bmh.ind == 0
        return 0
    else
    return bmh.heap[1]
end


    

    
Out[6]:





top (generic function with 1 method)

In [ ]:

    

function exchange!(bmh::BinaryMaxHeap, priority::Int)
    bmh.heap[1] = priority
    reshape_down!(bmh)
end


    

In [7]:

    

bmh = BinaryMaxHeap(10)


    

    
Out[7]:





BinaryMaxHeap([4646374576,4646374640,4646374704,4646380624,4646469712,4646381136,4646398032,4646398320,4646470128,4646403216],0)

In [8]:

    

for i in 1:10
    push!(bmh, i)
end


    

In [9]:

    

bmh


    

    
Out[9]:





BinaryMaxHeap([10,9,6,7,8,2,5,1,4,3],10)

In [10]:

    

pop!(bmh)


    

    
Out[10]:





10

In [11]:

    

for i in 1:9
    println(pop!(bmh))
end


    

    




9
8
7
6
5
4
3
2
1

In [12]:

    

bmh


    

    
Out[12]:





BinaryMaxHeap([1,1,2,1,3,2,5,1,4,3],0)

In [13]:

    

type IntegratedBinaryMaxHeap
    heap::Array{Int, 2}
    inds::Vector{Int}
    IntegratedBinaryMaxHeap(m_max::Int, n::Int) = new(Array(Int, m_max, n), zeros(Int, n))
end


    

In [14]:

    

function reshape_up!(ibmh::IntegratedBinaryMaxHeap, j::Int)
    current_ind = ibmh.inds[j]
    while true
        par = current_ind >> 1
        if par == 0 || ibmh.heap[current_ind, j] <= ibmh.heap[par, j]
            break
        else
            ibmh.heap[current_ind, j], ibmh.heap[par, j] = ibmh.heap[par, j], ibmh.heap[current_ind, j]
        end
        current_ind = par
    end
end


    

    
Out[14]:





reshape_up! (generic function with 2 methods)

In [15]:

    

function push!(bmh::IntegratedBinaryMaxHeap, j::Int, priority::Int)
    ibmh.inds[j] += 1
    ibmh.heap[ibmh.inds[j], j] = priority
    reshape_up!(ibmh, j)
end


    

    
Out[15]:





push! (generic function with 2 methods)

In [16]:

    

function reshape_down!(ibmh::IntegratedBinaryMaxHeap, j::Int)
    current_ind = 1
    while true
        c1, c2 = current_ind * 2, current_ind * 2 + 1
        if c1 > ibmh.inds[j]
            break
        elseif c2 > ibmh.inds[j]
            c = c1
        else
            c = ibmh.heap[c1, j] < ibmh.heap[c2, j] ? c2 : c1
        end
        if ibmh.heap[current_ind, j] < ibmh.heap[c, j]
            ibmh.heap[c, j], ibmh.heap[current_ind, j] = ibmh.heap[current_ind, j], ibmh.heap[c, j]
            current_ind = c
        else
            break
        end
    end
end


    

    
Out[16]:





reshape_down! (generic function with 2 methods)

In [17]:

    

function pop!(ibmh::IntegratedBinaryMaxHeap, j::Int)
    ret_val = ibmh.heap[1, j]
    ibmh.heap[1, j] = ibmh.heap[ibmh.inds[j], j]
    ibmh.inds[j] -= 1
    reshape_down!(ibmh, j)
    return ret_val
end


    

    
Out[17]:





pop! (generic function with 2 methods)

In [18]:

    

function top(ibmh::IntegratedBinaryMaxHeap, j::Int)
    if ibmh.inds[j] == 0
        return 0
    else
        return ibmh.heap[1, j]
    end
end


    

    
Out[18]:





top (generic function with 2 methods)

In [19]:

    

ibmh = IntegratedBinaryMaxHeap(10, 10)


    

    
Out[19]:





IntegratedBinaryMaxHeap([4565368864 4565368864 … 4565368864 4565368864; 4565368864 4565368864 … 4565368864 4565368864; … ; 4565368864 4565368864 … 4565368864 4565368864; 4565368864 4565368864 … 4565368864 0],[0,0,0,0,0,0,0,0,0,0])

In [20]:

    

push!(ibmh, 1, 5)


    

In [21]:

    

top(ibmh, 1)


    

    
Out[21]:





5

In [22]:

    

pop!(ibmh, 1)


    

    
Out[22]:





5

In [23]:

    

top(ibmh, 1)


    

    
Out[23]:





0