Library Reference

version 2.112.0

Internal API

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

std.container.binaryheap

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

This module is a submodule ofstd.container.

Sourcestd/container/binaryheap.d

License:

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

Authors:

Andrei Alexandrescu

Examples:

import std.algorithm.comparison : equal;import std.range : take;auto maxHeap = heapify([4, 7, 3, 1, 5]);assert(maxHeap.take(3).equal([7, 5, 4]));auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);assert(minHeap.take(3).equal([1, 3, 4]));

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

Implements abinary heapcontainer on top of a given random-access range type (usuallyT[]) or a random-access container type (usuallyArray!T). Thedocumentation ofBinaryHeap will refer to the underlying range orcontainer as thestore of the heap.

The binary heap induces structure over the underlying store such thataccessing the largest element (by using thefront property) is aΟ(1) operation and extracting it (by using theremoveFront() method) is done fast inΟ(log n) time.

Ifless is the less-than operator, which is the default option,thenBinaryHeap defines a so-called max-heap that optimizesextraction of thelargest elements. To define a min-heap,instantiate BinaryHeap with"a > b" as its predicate.

Simply extracting elements from aBinaryHeap container istantamount to lazily fetching elements ofStore in descendingorder. Extracting elements from theBinaryHeap to completionleaves the underlying store sorted in ascending order but, again,yields elements in descending order.

IfStore is a range, theBinaryHeap cannot grow beyond thesize of that range. IfStore is a container that supportsinsertBack, theBinaryHeap may grow by adding elements to thecontainer.

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 elementwriteln(h.front);// 16// a has the heap propertyassert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));

Examples:

BinaryHeap implements the standard input range interface, allowinglazy 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]));

this(Stores, size_tinitialSize = size_t.max);: Converts the stores into a heap. IfinitialSize is specified, only the firstinitialSize elements ins are transformed into a heap, after which the heap can grow up tor.length (ifStore is a range) or indefinitely (ifStore is a container withinsertBack). PerformsΟ(min(r.length, initialSize)) evaluations ofless.
voidacquire(Stores, size_tinitialSize = size_t.max);: Takes ownership of a store. After this, manipulatings may makethe heap work incorrectly.
voidassume(Stores, size_tinitialSize = size_t.max);: Takes ownership of a store assuming it already was organized as aheap.
autorelease();: Clears the heap. Returns the portion of the store from0 up tolength, which satisfies theheap property.
@property boolempty();: Returnstrue if the heap is empty,false otherwise.
@property BinaryHeapdup();: Returns a duplicate of the heap. Thedup method is available only if theunderlying store supports it.
@property size_tlength();: Returns the length of the heap.
@property size_tcapacity();: Returns the capacity of the heap, which is the length of theunderlying store (if the store is a range) or the capacity of theunderlying store (if the store is a container).
@property ElementType!Storefront();: Returns a copy of the front of the heap, which is the largest elementaccording toless.
voidclear();: Clears the heap by detaching it from the underlying store.
size_tinsert(ElementType!Storevalue);: Insertsvalue into the store. If the underlying store is a rangeandlength == capacity, throws an exception.
voidremoveFront(); aliaspopFront = removeFront;: Removes the largest element from the heap.
ElementType!StoreremoveAny();: Removes the largest element from the heap and returns a copy ofit. The element still resides in the heap's store. For performancereasons you may want to useremoveFront with heaps of objectsthat are expensive to copy.
voidreplaceFront(ElementType!Storevalue);: Replaces the largest element in the store withvalue.
boolconditionalInsert(ElementType!Storevalue);: If the heap has room to grow, insertsvalue into the store andreturnstrue. Otherwise, ifless(value, front), callsreplaceFront(value) and returns againtrue. Otherwise, leavesthe heap unaffected and returnsfalse. This method is useful inscenarios where the smallestk elements of a set of candidatesmust be collected.
boolconditionalSwap(ref ElementType!Storevalue);: Swapping is allowed if the heap is full. Ifless(value, front), themethod exchanges store.front and value and returnstrue. Otherwise, itleaves the heap unaffected and returnsfalse.

BinaryHeap!(Store, less)heapify(alias less = "a < b", Store)(Stores, size_tinitialSize = size_t.max);

Convenience function that returns aBinaryHeap!Store objectinitialized withs andinitialSize.

Examples:

import std.conv : to;import std.range.primitives;{// example from "Introduction to Algorithms" Cormen et al., p 146int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];auto h =heapify(a);    h =heapify!"a < b"(a);    writeln(h.front);// 16    writeln(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);        writeln(witness.front);// h.front    }assert(witness.empty);}{int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];int[] b =newint[a.length];    BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);foreach (e; a)    {        h.insert(e);    }    writeln(b);// [16, 14, 10, 8, 7, 3, 9, 1, 4, 2]}

Examples:

Example for unintuitive behaviourIt is important not to use the Store after a Heap has been instantiated fromit, at least in the cases of Dynamic Arrays. For example, inserting a new elementin a Heap, which is using a Dyamic Array as a Store, will cause a reallocation ofthe Store, if the Store is already full. The Heap will not point anymore to theoriginal Dyamic Array, but point to a new Dynamic Array.

import std.stdio;import std.algorithm.comparison : equal;import std.container.binaryheap;int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];auto h =heapify(a);// Internal representation of Binary Heap treeassert(a.equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));h.replaceFront(30);// Value 16 was replaced by 30assert(a.equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));// Making changes to the Store will be seen in the Heapa[0] = 40;writeln(h.front());// 40// Inserting a new element will reallocate the Store, leaving// the original Store unchanged.h.insert(20);assert(a.equal([40, 14, 10, 8, 7, 9, 3, 2, 4, 1]));// Making changes to the original Store will not affect the Heap anymorea[0] = 60;writeln(h.front());// 40

Movatterモバイル変換

Library Reference

std.container.binaryheap