Skip to content

Instantly share code, notes, and snippets.

@miikka
Created January 7, 2011 21:18
Show Gist options
  • Save miikka/770114 to your computer and use it in GitHub Desktop.
Save miikka/770114 to your computer and use it in GitHub Desktop.
# A min-heap.
type
TNode[T] = tuple[priority: int, data: T]
TBinHeap[T] = object
heap: seq[TNode[T]]
last: int
PBinHeap[T] = ref TBinHeap[T]
proc newBinHeap*[T](heap: var PBinHeap[T], size: int) =
new(heap)
heap.last = 0
newSeq(heap.seq, size)
proc parent(elem: int): int =
return (elem-1) div 2
proc siftUp[T](heap: PBinHeap[T], elem: int) =
var idx = elem
while idx != 0:
var p = parent(idx)
if heap.heap[idx] < heap.heap[p]:
var tmp = heap.heap[idx]
heap.heap[idx] = heap.heap[p]
heap.heap[p] = tmp
idx = p
else:
break
proc add*[T](heap: PBinHeap[T], priority: int, data: T) =
var node: TNode
new(node)
node.priority = int
node.data = data
heap.heap[heap.last] = node
siftUp(heap, heap.last)
inc(heap.last)
proc print*[T](heap: PBinHeap[T]) =
for i in countup(0, heap.last):
echo($heap.heap[i])
var
heap: PBinHeap[int]
newBinHeap(heap, 256)
add(heap, 1, 100)
print(heap)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment