std.container.binaryheap

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.

Source: std/container/binaryheap.d

Copyright

2010- Andrei Alexandrescu. All rights reserved by the respective holders.

License

Distributed under the Boost Software License, Version 1.0.

(See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).

Authors

Andrei Alexandrescu
struct BinaryHeap
fn heapify

Types 1

structBinaryHeap(Store, alias less = "a < b") if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))

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.

Fields
private RefCounted!(Data, RefCountedAutoInitialize.no) _payload
Methods
private Store _store() @property ref
private size_t _length() @property ref
private void assertValid()
void pop(Store store)
void acquire(Store s, size_t initialSize = size_t.max)Takes ownership of a store. After this, manipulating `s` may make the heap work incorrectly.
void assume(Store s, size_t initialSize = size_t.max)Takes ownership of a store assuming it already was organized as a heap.
auto release()Clears the heap. Returns the portion of the store from `0` up to `length`, which satisfies the https://en.wikipedia.org/wiki/Heap(datastructure, heap property).
bool empty() @propertyReturns `true` if the heap is empty, `false` otherwise.
size_t length() @propertyReturns the length of the heap.
size_t capacity() @propertyReturns 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).
ElementType!Store front() @propertyReturns a copy of the front of the heap, which is the largest element according to `less`.
void clear()Clears the heap by detaching it from the underlying store.
size_t insert(ElementType!Store value)Inserts `value` into the store. If the underlying store is a range and length == capacity, throws an exception.
void removeFront()Removes the largest element from the heap.
ElementType!Store 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 th...
void replaceFront(ElementType!Store value)Replaces the largest element in the store with `value`.
bool conditionalInsert(ElementType!Store value)If the heap has room to grow, inserts `value` into the store and returns `true`. Otherwise, if less(value), calls replaceFront(value) and returns again `true`. Otherwise, leaves the heap unaffected...
bool conditionalSwap(ref ElementType!Store value)Swapping is allowed if the heap is full. If less(value), the method exchanges store.front and value and returns `true`. Otherwise, it leaves the heap unaffected and returns `false`.
Constructors
this(Store s, size_t initialSize = size_t.max)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 `Stor...
Nested Templates
Data

Functions 1

fnBinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s, size_t initialSize = size_t.max)Convenience function that returns a `BinaryHeap!Store` object initialized with `s` and `initialSize`.