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:

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

Usage with custom objects

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

Example:

  1. import std/heapqueue
  2. type Job = object
  3.   priority: int
  5. proc `<`(a, b: Job): bool = a.priority < b.priority
  7. var jobs = initHeapQueue[Job]()
  8. jobs.push(Job(priority: 1))
  9. jobs.push(Job(priority: 2))
  11. assert jobs[0].priority == 1

Imports

since

Types

  1. HeapQueue[T] = object

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

Procs

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

Turns a heap into its string representation.

Example:

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

Source Edit 

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

Accesses the i-th element of heap. Source Edit 

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

Removes all elements from heap, making it empty.

Example:

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

Source Edit 

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

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

Example:

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

Source Edit 

  1. 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:

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

Source Edit 

  1. 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:

Source Edit 

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

Returns the number of elements of heap.

Example:

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

Source Edit 

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

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

Example:

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

Source Edit 

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

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

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

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

See also:

Example:

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

Source Edit 

  1. 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:

Example:

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

Source Edit 

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

Creates a new HeapQueue that contains the elements of x.

See also:

Example:

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

Source Edit