☰

# std/heapqueue

Theme:

- Manual
- Standard library
- Index
- Compiler docs
- Fusion docs
- devel, stable

Search:
Source Edit

The `heapqueue` module implements a binary heap data structure that can be used as a priority queue. They are represented as arrays for which `a[k] <= a[2*k+1]` and `a[k] <= a[2*k+2]` for all indices `k` (counting elements from 0). The interesting property of a heap is that `a[0]` is always its smallest element.

# Basic usage

Example:

    import std/heapqueue
    var heap = [8, 2].toHeapQueue
    heap.push(5)
    # the first element is the lowest element
    assert heap[0] == 2
    # remove and return the lowest element
    assert heap.pop() == 2
    # the lowest element remaining is 5
    assert heap[0] == 5

# Usage with custom objects

To use a `HeapQueue` with a custom object, the `<` operator must be implemented.

Example:

    import std/heapqueue
    type Job = object
      priority: int

    proc `<`(a, b: Job): bool = a.priority < b.priority

    var jobs = initHeapQueue[Job]()
    jobs.push(Job(priority: 1))
    jobs.push(Job(priority: 2))

    assert jobs[0].priority == 1

# Imports

since, assertions

# Types

    HeapQueue[T] = object

  A heap queue, commonly known as a priority queue. Source Edit

# Procs

    proc `$`[T](heap: HeapQueue[T]): string

  Turns a heap into its string representation.

  Example:

      let heap = [1, 2].toHeapQueue
      assert $heap == "[1, 2]"

  Source Edit

    proc `[]`[T](heap: HeapQueue[T]; i: Natural): lent T {.inline.}

  Accesses the i-th element of `heap`. Source Edit

    proc clear[T](heap: var HeapQueue[T])

  Removes all elements from `heap`, making it empty.

  Example:

      var heap = [9, 5, 8].toHeapQueue
      heap.clear()
      assert heap.len == 0

  Source Edit

    proc contains[T](heap: HeapQueue[T]; x: T): bool

  Returns true if `x` is in `heap` or false if not found. This is a shortcut for `find(heap, x) >= 0`. Source Edit

    proc del[T](heap: var HeapQueue[T]; index: Natural)

  Removes the element at `index` from `heap`, maintaining the heap invariant.

  Example:

      var heap = [9, 5, 8].toHeapQueue
      heap.del(1)
      assert heap[0] == 5
      assert heap[1] == 8

  Source Edit

    proc find[T](heap: HeapQueue[T]; x: T): int

  Linear scan to find the index of the item `x` or -1 if not found.

  Example:

      let heap = [9, 5, 8].toHeapQueue
      assert heap.find(5) == 0
      assert heap.find(9) == 1
      assert heap.find(777) == -1

  Source Edit

    proc initHeapQueue[T](): HeapQueue[T]

  Creates a new empty heap.

  Heaps are initialized by default, so it is not necessary to call this function explicitly.

  See also:

  - toHeapQueue proc
  Source Edit

    proc len[T](heap: HeapQueue[T]): int {.inline.}

  Returns the number of elements of `heap`.

  Example:

      let heap = [9, 5, 8].toHeapQueue
      assert heap.len == 3

  Source Edit

    proc pop[T](heap: var HeapQueue[T]): T

  Pops and returns the smallest item from `heap`, maintaining the heap invariant.

  Example:

      var heap = [9, 5, 8].toHeapQueue
      assert heap.pop() == 5

  Source Edit

    proc push[T](heap: var HeapQueue[T]; item: sink T)

  Pushes `item` onto `heap`, maintaining the heap invariant. Source Edit

    proc pushpop[T](heap: var HeapQueue[T]; item: sink T): T

  Fast version of a `push()` followed by a `pop()`.

  See also:

  - replace proc

  Example:

      var heap = [5, 12].toHeapQueue
      assert heap.pushpop(6) == 5
      assert heap.len == 2
      assert heap[0] == 6
      assert heap.pushpop(4) == 4

  Source Edit

    proc replace[T](heap: var HeapQueue[T]; item: sink T): T

  Pops and returns the current smallest value, and add the new item. This is more efficient than `pop()` followed by `push()`, and can be more appropriate when using a fixed-size heap. Note that the value returned may be larger than `item`! That constrains reasonable uses of this routine unless written as part of a conditional replacement.

  See also:

  - pushpop proc

  Example:

      var heap = [5, 12].toHeapQueue
      assert heap.replace(6) == 5
      assert heap.len == 2
      assert heap[0] == 6
      assert heap.replace(4) == 6

  Source Edit

    proc toHeapQueue[T](x: openArray[T]): HeapQueue[T]

  Creates a new HeapQueue that contains the elements of `x`.

  See also:

  - initHeapQueue proc

  Example:

      var heap = [9, 5, 8].toHeapQueue
      assert heap.pop() == 5
      assert heap[0] == 8

  Source Edit

# Iterators

    iterator items[T](heap: HeapQueue[T]): lent T {.inline.}

  Iterates over each item of `heap`. Source Edit