Lua library module "heap"

Author: Hans van der Meer
The Lua module heap is a C-module for the manipulation of heaps.

API

Remarks

  1. Functions that return the heap allow chaining of operations.
  2. An index out of range or nil forces an error.
  3. Negative index values are count backwards, -1 denoting the last entry.
  4. The value nil is not allowed as contents of the heap and will be ignored.
  5. Operations affecting heap contents ensure that afterwards the heap property is satisfied.

Create heap

heap.new() return empty heap
heap.new(name) optional name (string)
heap.new(capacity) initial capacity (positive number)
heap.new(compare) compare (function)
heap.new(-1) reverse default compare
new and create are synonyms
The function compare(elt1, elt2) shall return integer values +1, 0 or -1 for in-order, equal and out-order results, respectively. A return of +1 has the meaning that the values are out of order with respect to sorting. The parameters elt1, elt2 are the two elements to compare. If compare is not given the elements are by default compared arithmetically. The default compare function results in ascending heap values, change into descending by providing a -1.
The (name, capacity, compare, -1) parameters can be given in any order and in any combination. Other parameter values or types are acceptable, but will be silently ignored.

Check heap

h:check() true if heap property satisfied

Add element

h:insert(value) insert value, return heap
insert and add are synonyms
Tables are allowed as input value and are fully expanded to include their values.

Remove element

h:delete() return empty heap
h:delete(index) remove element at index
delete and remove are synonyms
In order to remove a specific element one has to first find it, thereafter use the resultant (valid) index to remove it.

Get element value

h:get(index [,index [...]]) return values at index
h:get() return table of all values
Requesting all values returns them in a table, because their number might be so large as to exhaust the capacity of the return stack.

Get element iterator

h:iterator() return forward iterator
h:iterator(-1) return reverse iterator
Requesting all values returns them in a table, because their number might be so large as to exhaust the capacity of the return stack.

Find element

h:find(value) return index of value or nil
h:find(value, index) start at given index
The normal search direction is from root to leaves; reverse search can be initiated by entering a negative index.

Order of elements

h:compare(elt1, elt2) return result of compare
h:sort() return sorted table of values
h:sort(-1) return reverse order sort
The compare function is supposed to return +1 for an in order result, 0 for equality and -1 for out of order compare result. The sorting is done with heapsort (taken from Jon Bently, Programming Pearls).

Query state

h:empty() true/false for heap empty/notempty
h:size(), #l heap size
h:ident() identity stamp, name or nil
heap.version() version of the module