Nestharus
o-o
- Reaction score
- 84
Good Tutorial on Binary Heaps and Priority Queues
Demo
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
</i>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
