1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
discard """
errormsg: "type mismatch: got <typedesc[int]> but expected 'int'"
file: "ttypenoval.nim"
line: 38
"""
# 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.heap, size)
#newSeq(heap.seq, size)
proc parent(elem: int): int {.inline.} =
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]:
swap(heap.heap[idx], heap.heap[p])
idx = p
else:
break
proc add*[T](heap: PBinHeap[T], priority: int, data: T) =
var node: TNode[T]
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)
|
