Menu

- Learn
- Documentation
  - Language Reference
  - Library Reference
  - Command-line Reference
  - Feature Overview
  - Articles
- Downloads
- Packages
- Community
  - Blog
  - Orgs using D
  - Twitter
  - Forums
  - IRC
  - Community Discord
  - Wiki
  - GitHub
  - Issues
  - Get involved
  - Contributors
  - Foundation
  - Security Team
  - Donate
  - Sponsors
- Resources
  - Tour
  - Books
  - Tutorials
  - Tools
  - Editors
  - IDEs
  - run.dlang.io
  - Visual D
  - Acknowledgments
  - D Style
  - Glossary
  - Sitemap

Search
Report a bug
If you spot a problem with this page, click here to create a Bugzilla 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.

# 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

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

struct `BinaryHeap`(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.
  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
      writeln(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 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(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.
  auto `release`();
    Clears the heap. Returns the portion of the store from 0 up to length, which satisfies the heap property.
  @property bool `empty`();
    Returns true if the heap is empty, false otherwise.
  @property BinaryHeap `dup`();
    Returns a duplicate of the heap. The `dup` method is available only if the underlying store supports it.
  @property size_t `length`();
    Returns the length of the heap.
  @property 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 ElementType!Store `front`();
    Returns 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`();
  alias `popFront` = 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 that are expensive to copy.
  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, 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.
  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!(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`.
  Examples:

      import std.conv : to;
      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);
          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 = new int[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 behaviour It is important not to use the Store after a Heap has been instantiated from it, at least in the cases of Dynamic Arrays. For example, inserting a new element in a Heap, which is using a Dyamic Array as a Store, will cause a reallocation of the Store, if the Store is already full. The Heap will not point anymore to the original 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 tree
      assert(a.equal([16, 14, 10, 8, 7, 9, 3, 2, 4, 1]));

      h.replaceFront(30);
      // Value 16 was replaced by 30
      assert(a.equal([30, 14, 10, 8, 7, 9, 3, 2, 4, 1]));

      // Making changes to the Store will be seen in the Heap
      a[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 anymore
      a[0] = 60;
      writeln(h.front()); // 40

Copyright © 1999-2023 by the D Language Foundation | Page generated by Ddoc on Sat Apr 1 13:10:08 2023