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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
discard """
matrix: "--mm:refc; --mm:orc"
"""
import std/heapqueue
import std/assertions
proc toSortedSeq[T](h: HeapQueue[T]): seq[T] =
var tmp = h
result = @[]
while tmp.len > 0:
result.add(pop(tmp))
proc heapProperty[T](h: HeapQueue[T]): bool =
for k in 0 .. h.len - 2: # the last element is always a leaf
let left = 2 * k + 1
if left < h.len and h[left] < h[k]:
return false
let right = left + 1
if right < h.len and h[right] < h[k]:
return false
true
template main() =
block: # simple sanity test
var heap = initHeapQueue[int]()
let data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data:
push(heap, item)
doAssert(heap == data.toHeapQueue)
doAssert(heap[0] == 0)
doAssert(heap.toSortedSeq == @[0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
block: # test del
var heap = initHeapQueue[int]()
let data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data: push(heap, item)
heap.del(0)
doAssert(heap[0] == 1)
heap.del(heap.find(7))
doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 5, 6, 8, 9])
heap.del(heap.find(5))
doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 6, 8, 9])
heap.del(heap.find(6))
doAssert(heap.toSortedSeq == @[1, 2, 3, 4, 8, 9])
heap.del(heap.find(2))
doAssert(heap.toSortedSeq == @[1, 3, 4, 8, 9])
doAssert(heap.find(2) == -1)
block: # test del last
var heap = initHeapQueue[int]()
let data = [1, 2, 3]
for item in data: push(heap, item)
heap.del(2)
doAssert(heap.toSortedSeq == @[1, 2])
heap.del(1)
doAssert(heap.toSortedSeq == @[1])
heap.del(0)
doAssert(heap.toSortedSeq == @[])
block: # testing the heap proeprty
var heap = [1, 4, 2, 5].toHeapQueue
doAssert heapProperty(heap)
heap.push(42)
doAssert heapProperty(heap)
heap.push(0)
doAssert heapProperty(heap)
heap.push(3)
doAssert heapProperty(heap)
heap.push(3)
doAssert heapProperty(heap)
# [0, 3, 1, 4, 42, 2, 3, 5]
discard heap.pop()
doAssert heapProperty(heap)
discard heap.pop()
doAssert heapProperty(heap)
heap.del(2)
doAssert heapProperty(heap)
# [2, 3, 5, 4, 42]
discard heap.replace(12)
doAssert heapProperty(heap)
discard heap.replace(1)
doAssert heapProperty(heap)
discard heap.pushpop(2)
doAssert heapProperty(heap)
discard heap.pushpop(0)
doAssert heapProperty(heap)
static: main()
main()
|
