Report a bug

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

Improve this page

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
a local clone.

# mir.container.binaryheap

This module provides a BinaryHeap (aka priority queue)
adaptor that makes a binary heap out of any user-provided random-access range.

Current implementation is suitable for Mir/BetterC concepts.
This module is a submodule of mir.container.

License:

Distributed under the Boost Software License, Version 1.0.

Authors:

Andrei Alexandrescu (original Phobos code), Ilya Yaroshenko (Mir & BetterC rework).

Examples:

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 146import 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@@@

Copyright © 1999-2018 by the D Language Foundation | Page generated by
Ddoc on Thu Nov 29 22:36:26 2018