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.

https://nim-lang.org/docs/heapqueue.html