[Snippet] Priority Queue

[Nestharus]

Good Tutorial on Binary Heaps and Priority Queues

library PQ /* v1.0.0.2
*************************************************************************************
*
*   Priority Queue
*
*       i.e.
*           struct Test extends array
*               implement PQ
*
*               //code
*
*           endstruct
*
************************************************************************************
*
*   */uses/*
*
*       */ Table /*       hiveworkshop.com/forums/jass-functions-413/snippet-new-table-188084/
*       */ BH /*          hiveworkshop.com/forums/submissions-414/snippet-minimum-binary-heap-199353/
*
************************************************************************************
*
*   static readonly thistype floor
*       -   The node with the floor value (max or min)
*
*   static method add takes integer value returns thistype
*       -   Adds a new value and returns the node that has it.
*   static method remove takes nothing returns nothing
*       -   Removes the floor value node
*
************************************************************************************/
    module PQ
        implement BH
        
        private static thistype array n     //next
        private static thistype array l     //last
        private static Table t              //table
        private static method onInit takes nothing returns nothing
            set t=Table.create()
        endmethod
        static method operator floor takes nothing returns thistype
            return n[thistype(1).node]
        endmethod
        static method add takes integer v returns thistype
            local thistype i=t[v]
            local thistype m=allocate(v)
            set n[m]=0
            if (0==i) then
                set i=insert(v)
                set t[v]=i
                set l[i]=i
            endif
            set n[l[i]]=m
            set l[i]=m
            return m
        endmethod
        static method remove takes nothing returns nothing
            local thistype m
            local thistype k
            if (0<size) then
                set m=thistype(1).node
                set k=n[m]
                set n[m]=n[k]
                call k.deallocate()
                if 0==n[m] then
                    call t.remove(m.value)
                    call delete(1)
                endif
            endif
        endmethod
    endmodule
endlibrary

 

[Nestharus]

Updated

 

[Bribe]

It's a priority queue I guess. Doesn't mean much to me.

I am trying to figure out why you use node 1 for BH and for this, when node seems to me like it is actually allocated by the user - why not use node 0?

 

[Nestharus]

It is used by the user, lol, and #1 is always the minimum or maximum value : ).

 

[Bribe]

Aha, now it makes sense thanks

 

[Nestharus]

Usually, when someone uses a priority queue, they only ever need access to the head, not the rest of the nodes. As this can then essentially be coded using only a Binary Heap and this doesn't work with the latest Binary Heap anyways, this should be graveyarded =).