Struct std.container.binaryheap.BinaryHeap
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.
struct BinaryHeap(Store, alias less)
if (isRandomAccessRange!Store || isRandomAccessRange!(typeof(Store .init[])));
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.
Constructors
Name | Description |
---|---|
this
(s, initialSize)
|
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 (if Store is a range) or indefinitely (if
Store is a container with insertBack ). Performs
Ο(min(r ) evaluations of less .
|
Properties
Name | Type | Description |
---|---|---|
capacity [get]
|
size_t | 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). |
dup [get]
|
BinaryHeap | Returns a duplicate of the heap. The dup method is available only if the
underlying store supports it.
|
empty [get]
|
bool | Returns true if the heap is empty, false otherwise.
|
front [get]
|
ElementType!Store | Returns a copy of the front of the heap, which is the largest element
according to less .
|
length [get]
|
size_t | Returns the length of the heap. |
Methods
Name | Description |
---|---|
acquire
(s, initialSize)
|
Takes ownership of a store. After this, manipulating s may make
the heap work incorrectly.
|
assume
(s, initialSize)
|
Takes ownership of a store assuming it already was organized as a heap. |
clear
()
|
Clears the heap by detaching it from the underlying store. |
conditionalInsert
(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.
|
conditionalSwap
(value)
|
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 .
|
insert
(value)
|
Inserts value into the store. If the underlying store is a range
and length == capacity , throws an exception.
|
release
()
|
Clears the heap. Returns the portion of the store from 0 up to
length , which satisfies the heap property.
|
removeAny
()
|
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.
|
removeFront
()
|
Removes the largest element from the heap. |
replaceFront
(value)
|
Replaces the largest element in the store with value .
|
Aliases
Name | Description |
---|---|
popFront
|
Removes the largest element from the heap. |
Example
Example from "Introduction to Algorithms" Cormen et al, p 146
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 ]));
Example
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]));
Authors
License
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).