Reading:
Heap Binary Heap
Functions
new_Heap() - O(1)
Heap_size() - O(1)
Heap_insert() - O(log n)
Heap_removeMin() - O(log n)
Heap_peekMin() - O(1)
Code
Main.agc
#include "Heap.Implementation.agc"
gosub initHeap
//////////////
heap as Heap_UDT
heap = new_Heap()
for i = 1 to 10
Heap_insert(heap, new_HeapElement())
next i
do
for i = 1 to heap.elements.length
print(heap.elements[i].heap#)
next i
if getRawKeyPressed(32) then Heap_removeMin(heap) //space
sync()
loop
function new_HeapElement()
e as HeapElement_UDT
e.heap# = Random(0, 10000)/1000.0
endfunction einitHeap:
#constant true = 1
#constant false = 0
type Heap_UDT
elements as HeapElement_UDT[] //always contains a placeholder at index 0
size
endtype
type HeapElement_UDT //Your UDT must resemble this UDT
heap# //Number for the heap to use when sorting. Call it whatever you'd like (don't forget to change it throughout the functions). It can also be an integer.
//Whatever else
endtype
return
function new_Heap()
heap as Heap_UDT
placeholder as HeapElement_UDT
heap.elements.insert(placeholder)
endfunction heap
function Heap_size(heap ref as Heap_UDT)
exitfunction heap.size
endfunction -1
function Heap_insert(heap ref as Heap_UDT, element as HeapElement_UDT)
heap.elements.insert(element)
heap.size = heap.size+1
Heap_heapifyUp(heap, heap.size)
endfunction
function Heap_removeMin(heap ref as Heap_UDT)
returnValue as HeapElement_UDT
returnValue = heap.elements[1]
heap.elements[1] = heap.elements[heap.size]
heap.elements.remove(heap.size)
heap.size = heap.size-1
Heap_heapifyDown(heap, 1)
endfunction returnValue
function Heap_peekMin(heap ref as Heap_UDT)
returnValue as HeapElement_UDT
returnValue = heap.elements[1]
endfunction returnValue
/////////////////////////////////////////////////////////////////////////
function Heap_heapifyUp(heap ref as Heap_UDT, i) //percolates up
tempElement as HeapElement_UDT
while i/2 > 0
if Heap_elementLessThan(heap.elements[i], heap.elements[i/2])
tempElement = heap.elements[i/2]
heap.elements[i/2] = heap.elements[i]
heap.elements[i] = tempElement
endif
i = i/2
endwhile
endfunction
function Heap_heapifyDown(heap ref as Heap_UDT, i) //percolates down
tempElement as HeapElement_UDT
while i*2 <= heap.size
minChild = Heap_minChild(heap, i)
if Heap_elementGreaterThan(heap.elements[i], heap.elements[minChild])
tempElement = heap.elements[i]
heap.elements[i] = heap.elements[minChild]
heap.elements[minChild] = tempElement
endif
i = minChild
endwhile
endfunction
function Heap_minChild(heap ref as Heap_UDT, i)
if i*2+1 > heap.size
exitfunction i*2
else
if Heap_elementLessThan(heap.elements[i*2], heap.elements[i*2+1])
exitfunction i*2
else
exitfunction i*2+1
endif
endif
endfunction -1
/////////////////////////////////////////////////////////////////////////
function Heap_elementLessThan(a ref as HeapElement_UDT, b ref as HeapElement_UDT)
if a.heap# < b.heap# then exitfunction true
endfunction false
function Heap_elementGreaterThan(a ref as HeapElement_UDT, b ref as HeapElement_UDT)
if a.heap# > b.heap# then exitfunction true
endfunction false
___________________________________________________________________________________
Hi everyone! I thought I'd share my code for a minimum sorted complete binary heap
(A fancy priority queue)
To use it with your own code:
1: Find and replace (Ctrl + H) "HeapElement_UDT" with your own UDT you wish to use.
2: Modify Heap_elementLessThan() and Heap_elementGreaterThan() to observe the variable you wish to sort by
(If using multiple different element UDTs with heaps) 3: Rename ALL heap functions to be specific to the UDT they store (Heap_size() is optional here)
|--> ex: MyUDTHeap_insert()
Final note: The Main.agc I included is just an example program I quickly put together. You shouldn't really inspect the contents of a heap as if it is an array. The functions provided are the proper way of interacting with a heap. However, I wanted to display how the heap stored its elements in this example.
