PairingHeap

Overview

Heap implementation with constant-time merge and get-first operations.

This implementation has the following complexity guarantees:

add, merge, get - O(1)
remove - amortized O(lg(size))
set - O(1) if new value is ordered before the old value, otherwise amortized O(lg(size))

By default, a PairingHeap uses the natural increasing order of the data, but any function which satisfies the ordering contract can be supplied to the new() method.

Examples of use:

> h1 = PairingHeap:make(1,3,5,2,4,6); print(h1)
/1, 6, 4, 2, 5, 3\
> node = h1:add(-1); print(h1) -- returns the node allocated
/-1, 1, 6, 4, 2, 5, 3\
> h1:set(node, 44); print(h1) -- adjust value, O(lg N) for decrease
/1, 6, 4, 2, 5, 3, 44\
> print(h1:remove()) -- removes and returns top/first element, O(lg N)
1
> print(h1:get()) -- the first element (equivalent to getFirst())
2
> h1:merge(heap(6,2,3,9)) -- merge in another heap, O(1)
> print(vector(h1:extractFirstK())) -- heapsort
[2, 2, 3, 3, 4, 5, 6, 6, 9, 44]

See: http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c13/pairing.htm for more information on pairing heaps

Summary

`new`	Constructs a new PairingHeap using the supplied ordering function (default is natural increasing order).
`make`	Creates and returns a new instance of self containing the elements passed in as vararg params.
`__eq`	Returns true if both heaps have the same size and both self:iter() and otherheap:iter() return the same sequence of values.
`add`	Adds val to this PairingHeap.
`addNode`	Adds this node to the heap and returns it.
`get`	Returns the first/topmost element in the heap.
`get`	Returns the first/topmost element in the heap.
`iter`	Returns an iterator over the values in the heap, starting from node, which defaults to the root.
`merge`	Merges another PairingHeap, pheap, in-place into this heap.
`nodeIter`	Returns an iterator over the NODES in the heap, starting from node (default is root).
`remove`	Removes the node from this PairingHeap and returns the value that was stored at that node.
`set`	Adjusts the value stored at node to be newVal and reestablishes the heap property.
`size`	Returns the number of elements in the PairingHeap.
`test`	Unit test.
`update`	Removes and reinserts node.
`toString`	Returns a string representation of heap.
`addAll`	Calls collection:add(e) for each e in iter(iterable).
`extractFirstK`	Returns an iterator which destructively removes and returns the first k elements from this heap.

Detail

`PairingHeap:new(orderFn)`

Constructs a new PairingHeap using the supplied ordering function (default is natural increasing order). If no ordering function is specified, the ordering function will become PairingHeap.cDefaultOrdering, which is by default ordering.INCREASING. Thus the heap created is a so-called 'min-heap': get() will return the smallest element. By setting PairingHeap.cDefaultOrdering to ordering.DECREASING or by explicitly passing ordering.DECREASING to this method, get() will return the largest element.

param orderFn: function meeting the ordering contract

`collections.make(self, ...)`

Creates and returns a new instance of self containing the elements passed in as vararg params.

If #args is 1, the argument is assumed to be iterable and its elements are added to the Collection.

Example, assuming Collection is a sequence type:

> print( Collection:make(1,2,3,4) )
[1, 2, 3, 4]
> print( Collection:make(iter.count(4) )
[1, 2, 3, 4]
> v = Collection:make(1,2,3,4); print( Collection:make(v) )
[1, 2, 3, 4]

This method is used as the make method for LinkedList, SkipVector, HashSet, SkipSet, QueueVector, and PairingHeap. It assumes that self has new() and addAll() methods.

`PairingHeap:__eq(otherheap)`

Returns true if both heaps have the same size and both self:iter() and otherheap:iter() return the same sequence of values.

`PairingHeap:add(val)`

Adds val to this PairingHeap.

param val: an element which is totaly ordered wrt all other elements in the heap

returns: the allocated node in the heap -- this reference can be passed as the first argument to the remove() or set() methods

time complexity: O(1)

`PairingHeap:addNode(node)`

Adds this node to the heap and returns it.

This method is part of the contract which enables a PairingHeap to be used in a MinMaxHeap; it should not normally be used by clients.

param node: a node returned by a prior call to add() returns the added node

`PairingHeap:get()`

Returns the first/topmost element in the heap.

The heap is not modified by the call; this merely 'peeks' at the top element.

time complexity: O(1) synonyms: getFirst

`PairingHeap:get()`

Returns the first/topmost element in the heap.

The heap is not modified by the call; this merely 'peeks' at the top element.

time complexity: O(1) synonyms: getFirst

`PairingHeap:iter(node)`

Returns an iterator over the values in the heap, starting from node, which defaults to the root.

The elements of the iteration are not returned in sorted order, although the first element returned will by default be the topmost element of the heap.

param node: a node returned by a prior call to add() (default is root of heap)

`PairingHeap:merge(pheap)`

Merges another PairingHeap, pheap, in-place into this heap.

This heap is modified and pheap is invalidated as a result of this call.

returns: this PairingHeap (to allow chaining) time complexity: O(1)

`PairingHeap:nodeIter(node)`

Returns an iterator over the NODES in the heap, starting from node (default is root).

The nodes returned by the iteration could be passed to the set() or remove() methods, although it is not safe to modify the heap while iterating.

param node: a node returned by a prior call to add() (default is root)

`PairingHeap:remove(node)`

Removes the node from this PairingHeap and returns the value that was stored at that node. param node: a node returned by a prior call to add() time complexity: amortized O(lg(size))

`PairingHeap:replaceRoot(newRoot)`

`PairingHeap:set(node, newVal)`

Adjusts the value stored at node to be newVal and reestablishes the heap property.

param node: a node returned by a prior call to add() time complexity: O(1) if newVal comes before the old val according to the ordering function of the heap; O(lg(size)) if newVal comes after

`PairingHeap:size()`

Returns the number of elements in the PairingHeap.

`PairingHeap:test()`

Unit test.

`PairingHeap:update(node)`

Removes and reinserts node.

This method is used for re-establishing the heap property after the value stored at node has been altered.

`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\

`collections.addAll(collection, iterable)`

Calls collection:add(e) for each e in iter(iterable).

`PairingHeap.cDefaultOrdering`

The default ordering for elements in a PairingHeap (initially ordering.INCREASING)

`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]