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.


HeapQueue[T] = distinct seq[T]


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
Licensed under the MIT License.