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

Basic usage

import heapqueue

var heap = initHeapQueue[int]()
heap.push(8)
heap.push(2)
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 object

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

import 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

Types

HeapQueue[T] = object data: seq[T]: A heap queue, commonly known as a priority queue. Source Edit

Procs

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

Create a new empty heap. Source Edit

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

Return the number of elements of heap. Source Edit

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

Access the i-th element of heap. Source Edit

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

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

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

Pop and return the smallest item from heap, maintaining the heap invariant. Source Edit

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

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

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

Pop and return 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:

if item > heap[0]:
    item = replace(heap, item)

Source Edit

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

Fast version of a push followed by a pop. Source Edit

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

Remove all elements from heap, making it empty.

Examples:

var heap = initHeapQueue[int]()
heap.push(1)
heap.clear()
assert heap.len == 0

Source Edit

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

Turn a heap into its string representation.

Examples:

var heap = initHeapQueue[int]()
heap.push(1)
heap.push(2)
assert $heap == "[1, 2]"

Source Edit

proc newHeapQueue[T](): HeapQueue[T] {...}{.deprecated: "Deprecated since v0.20.0: use \'initHeapQueue\' instead.".}

Deprecated: Deprecated since v0.20.0: use 'initHeapQueue' instead.

Source Edit

proc newHeapQueue[T](heap: var HeapQueue[T]) {...}{. deprecated: "Deprecated since v0.20.0: use \'clear\' instead.".}

Deprecated: Deprecated since v0.20.0: use 'clear' instead.

Source Edit