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.