mir.container.binaryheap

import mir.algorithm.iteration : equal;
import std.range : takeExactly;
static a = [4, 7, 3, 1, 5], b = [7, 5, 4];
auto maxHeap = a.heapify;
assert((&maxHeap).takeExactly(3).equal(b));

static c = [4, 7, 3, 1, 5], d = [1, 3, 4];
auto minHeap = c.heapify!"a > b";
assert((&minHeap).takeExactly(3).equal(d));

struct BinaryHeap(alias less = "a < b", Store) 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 not a container, 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.

Examples:

Example from "Introduction to Algorithms" Cormen et al, p 146

import mir.algorithm.iteration : 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 ]));

Examples:

BinaryHeap implements the standard input range interface, allowing lazy iteration of the underlying range in descending order.

import mir.algorithm.iteration : equal;
import std.range : takeExactly;
int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
auto heap = heapify(a);
auto top5 = (&heap).takeExactly(5);
assert(top5.equal([16, 14, 10, 9, 8]));

size_t _length;

Store _store;

The payload includes the support store and the effective length

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

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.

const @property scope size_t length();

Returns the length of the heap.

const @property scope bool empty();

Returns true if the heap is empty, false otherwise.

const @property scope size_t capacity();

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

@property ref scope ElementType!Store front() return;

Returns a front of the heap, which is the largest element according to less.

scope size_t insert(ElementType!Store value);

Inserts value into the store. If the underlying store is a range and length == capacity, throws an AssertException.

scope void removeFront();

alias popFront = removeFront;

Removes the largest element from the heap.

ref scope auto removeAny();

Removes the largest element from the heap and returns 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.

scope void replaceFront(ElementType!Store value);

Replaces the largest element in the store with value.

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

scope bool conditionalSwap(ref 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.

BinaryHeap!(less, Store) 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.

Examples:

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);
    assert(h.front == 16);
    assert(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);
        assert(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!("a < b", int[]) h = BinaryHeap!("a < b", int[])(b, 0);
    foreach (e; a)
    {
        h.insert(e);
    }
    assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ]);
}

template HeapOps(alias less, Range)

Heap operations for random-access ranges

void heapSort()(Range r);

template because of @@@12410@@@

void buildHeap()(Range r);

template because of @@@12410@@@

bool isHeap()(Range r);

void siftDown()(Range r, size_t parent, immutable size_t end);

Sifts down r[parent] (which is initially assumed to be messed up) so the heap property is restored for r[parent .. end]. template because of @@@12410@@@

void percolate()(Range r, size_t parent, immutable size_t end);

Alternate version of siftDown that performs fewer comparisons, see https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort. The percolate process first sifts the parent all the way down (without comparing it against the leaves), and then a bit up until the heap property is restored. So there are more swaps but fewer comparisons. Gains are made when the final position is likely to end toward the bottom of the heap, so not a lot of sifts back are performed. template because of @@@12410@@@