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))

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

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

`PairingHeap:new(orderFn)`

param orderFn: function meeting the *ordering* contract

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

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

`PairingHeap:add(val)`

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

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()`

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

time complexity: O(1) synonyms: getFirst

`PairingHeap:get()`

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

time complexity: O(1) synonyms: getFirst

`PairingHeap:iter(node)`

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

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

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

`PairingHeap:replaceRoot(newRoot)`

`PairingHeap:set(node, newVal)`

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()`

`PairingHeap:test()`

`PairingHeap:update(node)`

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

`heaps.toString(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)`

`PairingHeap.cDefaultOrdering`

`heaps.extractFirstK(heap [, k])`

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]