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
|
@system unittest
{
import std.container.binaryheap;
import std.algorithm.comparison : equal;
import std.range : take;
auto maxHeap = heapify([4, 7, 3, 1, 5]);
assert(maxHeap.take(3).equal([7, 5, 4]));
auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
assert(minHeap.take(3).equal([1, 3, 4]));
}
@system unittest
{
import std.container.binaryheap;
import std.algorithm.comparison : equal;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// largest element
assert(h.front == 16);
// a has the heap property
assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
}
@system unittest
{
import std.container.binaryheap;
import std.algorithm.comparison : equal;
import std.range : take;
int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
auto top5 = heapify(a).take(5);
assert(top5.equal([16, 14, 10, 9, 8]));
}
@system unittest
{
import std.container.binaryheap;
import std.conv : to;
import std.range.primitives;
{
// example from "Introduction to Algorithms" Cormen et al., p 146
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
h = heapify!"a < b"(a);
assert(h.front == 16);
assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
for (; !h.empty; h.removeFront(), witness.popFront())
{
assert(!witness.empty);
assert(witness.front == h.front);
}
assert(witness.empty);
}
{
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
int[] b = new int[a.length];
BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
foreach (e; a)
{
h.insert(e);
}
assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
}
}
@system unittest
{
import std.container.binaryheap;
import std.stdio;
import std.algorithm.comparison : equal;
import std.container.binaryheap;
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// Internal representation of Binary Heap tree
assert(a.equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
h.replaceFront(30);
// Value 16 was replaced by 30
assert(a.equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
// Making changes to the Store will be seen in the Heap
a[0] = 40;
assert(h.front() == 40);
// Inserting a new element will reallocate the Store, leaving
// the original Store unchanged.
h.insert(20);
assert(a.equal([40, 14, 10, 8, 7, 9, 3, 2, 4, 1]));
// Making changes to the original Store will not affect the Heap anymore
a[0] = 60;
assert(h.front() == 40);
}
|
