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)); }
Example for unintuitive behaviour It is important not to use the Store after a Heap has been instantiated from it, at least in the cases of Dynamic Arrays. For example, inserting a new element in a Heap, which is using a Dyamic Array as a Store, will cause a reallocation of the Store, if the Store is already full. The Heap will not point anymore to the original Dyamic Array, but point to a new Dynamic Array.
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);
Convenience function that returns a BinaryHeap!Store object initialized with s and initialSize.