[snippet] Maximum Binary Heap

[Nestharus]

Good Tutorial on Binary Heaps and Priority Queues

library MABH /* v1.0.0.1
*************************************************************************************
*
*   Maximum Binary Heap
*
************************************************************************************
*
*   static readonly thistype root
*       -   The node with the largest value
*   readonly thistype node
*       -   Node stored within heap position
*   readonly thistype heap
*       -   Heap position of node
*   static readonly integer size
*       -   Size of binary heap
*   readonly integer value
*       -   Sorted value (the value of the node)
*
*   static method insert takes integer sortValue returns thistype
*       -   Inserts a new node into the heap and returns it
*   static method delete takes thistype node returns nothing
*       -   Deletes node from heap
*
************************************************************************************/
    module MABH
        readonly static integer size=0
        readonly thistype node              //node
        private static thistype nc=0        //node instance count
        private static thistype array r     //node recycler
        readonly integer value
        readonly thistype heap
        static method operator root takes nothing returns thistype
            return thistype(1).node
        endmethod
        static method allocate takes integer v returns thistype
            local thistype i
            if (0==r[0]) then
                set i=nc+1
                set nc=i
            else
                set i=r[0]
                set r[0]=r[i]
            endif
            set i.value=v
            return i
        endmethod
        method deallocate takes nothing returns nothing
            set r[this]=r[0]
            set r[0]=this
        endmethod
        static method insert takes integer v returns thistype
            local thistype i=size+1         //heap node
            local thistype p=i/2            //parent
            local thistype m
            set size=i
            
            //allocate node
            if (0==r[0]) then
                set m=nc+1
                set nc=m
            else
                set m=r[0]
                set r[0]=r[m]
            endif
            set m.value=v
            
            loop
                exitwhen 0==p or v<p.node.value
                set i.node=p.node
                set i.node.heap=i
                set i=p
                set p=p/2
            endloop
            set i.node=m
            set m.heap=i
            
            return m
        endmethod
        static method delete takes thistype i returns nothing
            local thistype m
            local thistype h
            local thistype o
            if (0<size) then
                set m=i.node
                set r[m]=r[0]
                set r[0]=m
                loop
                    set m=i*2       //left
                    set o=m+1       //right
                    exitwhen 0==m.node and 0==o.node
                    if (0==o.node.value or m.node.value>o.node.value) then
                        set i.node=m.node
                        set i.node.heap=i
                        set i=m
                    else
                        set i.node=o.node
                        set i.node.heap=i
                        set i=o
                    endif
                    set i.node=0
                endloop
                set h=thistype(size).node       //last node
                set thistype(size).node=0
                set size=size-1                 //deallocate heap node
                if (0!=h) then
                    set m=i/2       //parent
                    set o=h.value   //value of last node
                    loop
                        exitwhen 0==m or integer(o)<m.node.value
                        set i.node=m.node
                        set i.node.heap=i
                        set i=m
                        set m=m/2
                    endloop
                    set i.node=h
                    set h.heap=i
                endif
            endif
        endmethod
    endmodule
endlibrary

Demo

struct Heap extends array
    implement MABH

    private static method onInit takes nothing returns nothing
        call insert(5)
        call insert(9)
        call insert(3)
        call insert(2)
        call insert(-1)
        call insert(16)
        loop
            exitwhen 0==size
            call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,I2S(root.value))
            call delete(1) //or call delete(root.heap), but delete 1 is faster
        endloop
        //16,9,5,3,2,-1
    endmethod
endstruct

 

[Magtheridon96]

You know, instead of two seperate resources, you could've uploaded a "Binary Heap" snippet. You could use a boolean to differentiate between Max and Min Heaps
Yes, I know it would be slower, but it would save some memory :/

 

[Bribe]

Graveyarded.