[snippet] Maximum Binary Heap

Nestharus

Level 31
Good Tutorial on Binary Heaps and Priority Queues

JASS:
``````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
JASS:
``````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``````

Last edited:

Magtheridon96

Level 36
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 :/

Replies
5
Views
1K
Replies
6
Views
2K
Replies
5
Views
1K
Replies
1
Views
958
Replies
17
Views
9K