#### Nestharus

##### o-o

- Reaction score
- 83

JASS:

```
library BH /* v3.0.0.2
*************************************************************************************
*
* Binary Heap
*
************************************************************************************
*
* Requires a compare method that compares the first value against a second value
* < for minimum
* > for maximum
*
* private static method compare takes thistype v1, thistype v2 returns boolean
*
* static readonly thistype root
* - The node with the smallest/biggest 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)
*
* method modify takes integer sortValue returns nothing
* - Modifies 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 BH
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 thistype value
readonly thistype heap
static method operator root takes nothing returns thistype
return thistype(1).node
endmethod
static method allocate takes thistype 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
method modify takes integer v returns nothing
local thistype i=heap
local thistype m
local thistype o
set value=v
//bubble moved node down
loop
set m=i*2 //left
set o=m+1 //right
exitwhen (0==m.node or compare(value,m.node.value)) and (0==o.node or compare(value,o.node.value))
if (0==o.node.value or (0!=m.node and compare(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
endloop
set i.node=this
set heap=i
endmethod
static method insert takes thistype 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 compare(p.node.value,v)
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 this=thistype(size).node
local thistype m
local thistype o
debug if (0<size) then
//deallocate deleted node
set m=i.node
set r[m]=r[0]
set r[0]=m
set thistype(size).node=0
set size=size-1
//bubble moved node down
loop
set m=i*2 //left
set o=m+1 //right
exitwhen (0==m.node or compare(value,m.node.value)) and (0==o.node or compare(value,o.node.value))
if (0==o.node.value or (0!=m.node and compare(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
endloop
set i.node=this
set heap=i
debug endif
endmethod
endmodule
endlibrary
</i>
```

**Demo**JASS:

```
struct Heap extends array
implement BH
private static method compare takes integer v1, integer v2 returns boolean
return v1<v2
endmethod
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
//-1,2,3,5,9,16
endmethod
endstruct
```