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.

The binary heap induces structure over the underlying store such that accessing the largest element (by using the front property) is a O(1) operation and extracting it (by using the removeFront() method) is done fast in O(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.

struct BinaryHeap (

Store

alias less = "a < b"

) if (

isRandomAccessRange!(Store) ||

isRandomAccessRange!(typeof(Store.init[]))

) {

T min(T a, U b) via import std.algorithm.comparison : min;;

T move(T source) via import std.algorithm.mutation : move, swapAt;;

void swapAt(R r, size_t i1, size_t i2) via import std.algorithm.mutation : move, swapAt;;

T enforce(T value, Throwable ex) via import std.exception : enforce;;

template binaryFun(alias fun, string parm1Name = "a", string parm2Name = "b") via import std.functional : binaryFun;;

struct RefCounted(T, RefCountedAutoInitialize autoInit = RefCountedAutoInitialize.yes) via import std.typecons : RefCounted, RefCountedAutoInitialize;;

enum RefCountedAutoInitialize via import std.typecons : RefCounted, RefCountedAutoInitialize;;

this(Store s, size_t initialSize);

void acquire(Store s, size_t initialSize);

void assume(Store s, size_t initialSize);

auto release();

bool empty [@property getter];

static if(is(typeof( (Store s)(Store.init)) == Store))

BinaryHeap dup [@property getter];

size_t length [@property getter];

size_t capacity [@property getter];

ElementType!Store front [@property getter];

void clear();

size_t insert(ElementType!Store value);

void removeFront();

alias popFront = removeFront;

ElementType!Store removeAny();

void replaceFront(ElementType!Store value);

bool conditionalInsert(ElementType!Store value);

bool conditionalSwap(ElementType!Store value);

}

Constructors

this this(Store s, size_t 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.length (if Store is a range) or indefinitely (if Store is a container with insertBack). Performs O(min(r.length, initialSize)) evaluations of less.

Members

Aliases

popFront alias popFront = removeFront: Removes the largest element from the heap.

Functions

acquire void acquire(Store s, size_t initialSize): Takes ownership of a store. After this, manipulating s may make the heap work incorrectly.
assume void assume(Store s, size_t initialSize): Takes ownership of a store assuming it already was organized as a heap.
clear void clear(): Clears the heap by detaching it from the underlying store.
conditionalInsert bool conditionalInsert(ElementType!Store 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 bool conditionalSwap(ElementType!Store 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 size_t insert(ElementType!Store value): Inserts value into the store. If the underlying store is a range and length == capacity, throws an exception.
release auto release(): Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property.
removeAny 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 that are expensive to copy.
removeFront void removeFront(): Removes the largest element from the heap.
replaceFront void replaceFront(ElementType!Store value): Replaces the largest element in the store with value.

Properties

capacity size_t capacity [@property getter]: 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 BinaryHeap dup [@property getter]: Returns a duplicate of the heap. The dup method is available only if the underlying store supports it.
empty bool empty [@property getter]: Returns true if the heap is empty, false otherwise.
front ElementType!Store front [@property getter]: Returns a copy of the front of the heap, which is the largest element according to less.
length size_t length [@property getter]: Returns the length of the heap.

Examples

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
assert(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]));