Display the source code in std/container/binaryheap.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

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`	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`.

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`	Takes ownership of a store. After this, manipulating `s` may make the heap work incorrectly.
`assume`	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`	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`	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`	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`	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

Andrei Alexandrescu

License

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at ).

API Documentation

Struct std.container.binaryheap.BinaryHeap

Constructors

Properties

Methods

Aliases

Example

Example

Authors

License

Struct `std.container.binaryheap.BinaryHeap`