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