heapify

1 import std.conv : to;
2 import std.range.primitives;
3 {
4     // example from "Introduction to Algorithms" Cormen et al., p 146
5     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
6     auto h = heapify(a);
7     h = heapify!"a < b"(a);
8     assert(h.front == 16);
9     assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
10     auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
11     for (; !h.empty; h.removeFront(), witness.popFront())
12     {
13         assert(!witness.empty);
14         assert(witness.front == h.front);
15     }
16     assert(witness.empty);
17 }
18 {
19     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
20     int[] b = new int[a.length];
21     BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
22     foreach (e; a)
23     {
24         h.insert(e);
25     }
26     assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
27 }