- Joined
- Jul 10, 2007
- Messages
- 6,306
Good Tutorial on Binary Heaps and Priority Queues
JASS:
library PS /* v1.0.0.2
*************************************************************************************
*
* Priority Stack
*
* i.e.
* struct Test extends array
* implement PS
*
* //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 PS
implement BH
private static thistype array n //next
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 n[i]=0
endif
set n[m]=n[i]
set n[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
Last edited:
