heaps

Overview

Module containing methods shared across heap implementations.

Currently, the Sano library contains only one heap implementation (PairingHeap).

Summary

extractFirstKReturns an iterator which destructively removes and returns the first k elements from this heap.
toStringReturns a string representation of heap.

Detail

heaps.extractFirstK(heap [, k])

Returns an iterator which destructively removes and returns the first k elements from this heap.

If k is unspecified, the entire heap is drained by the returned iterator. If k is greater than heap:size(), an error is thrown.

The typical use for this method would be in a heapsort or a partial sort, for example:

> v = vector(iter.count(15)); v:shuffle(); print(v)
[4, 9, 3, 8, 12, 2, 14, 1, 6, 11, 13, 10, 7, 15, 5]
> h = heap(v); print(h)
/1, 5, 15, 7, 10, 13, 11, 6, 2, 14, 3, 12, 8, 4, 9\
> print(vector(h:extractFirstK(10)))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

heaps.toString(heap)

Returns a string representation of heap.

The order in which elements are displayed is unspecified, except that the top element of the heap will always appear first.

Example:

> h = heap(1,32,2,5,2,0)
> print(h) -- 0 is top of heap, appears first in string repr.
/0, 1, 2, 5, 2, 32\