/Nim

# Module heapqueue

Heap queue algorithm (a.k.a. priority queue). Ported from Python heapq.

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. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that a[0] is always its smallest element.

## Types

`HeapQueue[T] = distinct seq[T]`

## Procs

`proc newHeapQueue[T](): HeapQueue[T] {...}{.inline.}`
`proc newHeapQueue[T](h: var HeapQueue[T]) {...}{.inline.}`
`proc len[T](h: HeapQueue[T]): int {...}{.inline.}`
`proc `[]`[T](h: HeapQueue[T]; i: int): T {...}{.inline.}`
`proc push[T](heap: var HeapQueue[T]; item: T)`
Push item onto heap, maintaining the heap invariant.
`proc pop[T](heap: var HeapQueue[T]): T`
Pop the smallest item off the heap, maintaining the heap invariant.
`proc del[T](heap: var HeapQueue[T]; index: int)`
Removes element at index, maintaining the heap invariant.
`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:
`proc pushpop[T](heap: var HeapQueue[T]; item: T): T`
Fast version of a push followed by a pop.

© 2006–2018 Andreas Rumpf