std/heapqueue
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
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 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:
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:
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:
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:
Example:
var heap = [9, 5, 8].toHeapQueue
assert heap.pop() == 5
assert heap[0] == 8
Source Edit