This module provides a BinaryHeap
(aka priority queue) adaptor that makes a binary heap out of any user-provided random-access range.
This module is a submodule of std.container
.
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]));
Implements a binary heap container on top of a given random-access range type (usually T[]
) or a random-access container type (usually Array!T
). The documentation of BinaryHeap
will refer to the underlying range or container as the store of the heap.
The binary heap induces structure over the underlying store such that accessing the largest element (by using the front
property) is a Ο(1
) operation and extracting it (by using the removeFront()
method) is done fast in Ο(log n
) time.
If less
is the less-than operator, which is the default option, then BinaryHeap
defines a so-called max-heap that optimizes extraction of the largest elements. To define a min-heap, instantiate BinaryHeap with "a > b"
as its predicate.
Simply extracting elements from a BinaryHeap
container is tantamount to lazily fetching elements of Store
in descending order. Extracting elements from the BinaryHeap
to completion leaves the underlying store sorted in ascending order but, again, yields elements in descending order.
If Store
is a range, the BinaryHeap
cannot grow beyond the size of that range. If Store
is a container that supports insertBack
, the BinaryHeap
may grow by adding elements to the container.
import std.algorithm.comparison : equal; int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ]; auto h = heapify(a); // largest element writeln(h.front); // 16 // a has the heap property assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
BinaryHeap
implements the standard input range interface, allowing lazy iteration of the underlying range in descending order. 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]));
Converts the store s
into a heap. If initialSize
is specified, only the first initialSize
elements in s
are transformed into a heap, after which the heap can grow up to r.length
(if Store
is a range) or indefinitely (if Store
is a container with insertBack
). Performs Ο(min(r.length, initialSize)
) evaluations of less
.
Takes ownership of a store. After this, manipulating s
may make the heap work incorrectly.
Takes ownership of a store assuming it already was organized as a heap.
Clears the heap. Returns the portion of the store from 0
up to length
, which satisfies the heap property.
Returns true
if the heap is empty, false
otherwise.
Returns a duplicate of the heap. The dup
method is available only if the underlying store supports it.
Returns the length of the heap.
Returns the capacity of the heap, which is the length of the underlying store (if the store is a range) or the capacity of the underlying store (if the store is a container).
Returns a copy of the front of the heap, which is the largest element according to less
.
Clears the heap by detaching it from the underlying store.
Inserts value
into the store. If the underlying store is a range and length == capacity
, throws an exception.
Removes the largest element from the heap.
Removes the largest element from the heap and returns a copy of it. The element still resides in the heap's store. For performance reasons you may want to use removeFront
with heaps of objects that are expensive to copy.
Replaces the largest element in the store with value
.
If the heap has room to grow, inserts value
into the store and returns true
. Otherwise, if less(value, front)
, calls replaceFront(value)
and returns again true
. Otherwise, leaves the heap unaffected and returns false
. This method is useful in scenarios where the smallest k
elements of a set of candidates must be collected.
Swapping is allowed if the heap is full. If less(value, front)
, the method exchanges store.front and value and returns true
. Otherwise, it leaves the heap unaffected and returns false
.
Convenience function that returns a BinaryHeap!Store
object initialized with s
and initialSize
.
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); writeln(h.front); // 16 writeln(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); writeln(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); } writeln(b); // [16, 14, 10, 8, 7, 3, 9, 1, 4, 2] }
© 1999–2018 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_container_binaryheap.html