File PairingHeap.h

↰ Parent directory (ADS/priority)

The PRIORITYQUEUE [see File PriorityQueue.h] on a pairing heap, beyond the book: the self-adjusting heap of Fredman, Sedgewick, Sleator and Tarjan, the simplest of the heaps with decrease-key and, in the experiments of Stasko and Vitter and of Larkin, Sen and Tarjan, the fastest one with pointers in practice.

Definition (ADS/priority/PairingHeap.h)

Detailed Description

The heap is one tree, each node not smaller than its parent, kept in the form child-sibling: a node points to its leftmost child and to its right sibling, and back to its left sibling, or to its parent if it is the leftmost child, so that a node is cut from its tree in O( 1 ). The linking of two trees makes the root of larger key the leftmost child of the other one. insert() links a tree of one node with the root; decrease() cuts the node with its subtree, unless it is the leftmost child and still not smaller than its parent, and links it with the root; deleteMin() removes the root and joins its children by two passes: the first links them in pairs from the left, the second links the results from the right into one tree. The amortized bounds known for the two passes are O( log n ) for deleteMin() and :math:` O( 2^{2 sqrt{log log n}} ) ` for insert() and decrease() (Pettie; O( 1 ) for insert(), Iacono), while Fredman proved that :math:` Omega( log log n ) ` is needed by decrease() in this family of heaps, against the O( 1 ) of the Fibonacci heap [see File FibonacciHeapPriorityQueue.h], whose constants are larger.

With Aux = true the heap is the auxiliary two-pass variant of Stasko and Vitter: the trees of insert() and decrease() go to a list beside the root, with a pointer to the least of the roots, so that each costs one comparison, and deleteMin() first joins the list by the multipass pairing (the trees linked in pairs from the front of a queue, the result to its back, until one is left) and links it with the root; it pays when the inserts outnumber the deleteMin()s.

The nodes come from an ObjectPool [see File ObjectPool.h], which takes back the node of deleteMin() for the next insert(), so that a node costs no call to the allocator. The two passes run in place on the sibling pointers, with no stack and no vector.

The contracts [see File Contract.h]: min(), minPriority() and deleteMin() need a heap that is not empty, decrease() a handle of a node of this heap and a priority not larger than its own; the invariant, checked on heaps of at most 1024 nodes, is the order of the heap, the links back and size() counting the nodes. The operations are defined in PairingHeap.tpp.

    1. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica 1(1-4), 111-129, 1986, doi:10.1007/BF01840439

    1. Stasko, J. S. Vitter, Pairing heaps: experiments and analysis, Communications of the ACM 30(3), 234-249, 1987, doi:10.1145/214748.214759

    1. Fredman, On the efficiency of pairing heaps and related data structures, Journal of the ACM 46(4), 473-501, 1999, doi:10.1145/320211.320214

  1. Iacono, Improved upper bounds for pairing heaps, Algorithm Theory - SWAT 2000, Lecture Notes in Computer Science 1851, 32-45, 2000, doi:10.1007/3-540-44985-X_5

  1. Pettie, Towards a final analysis of pairing heaps, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 174-183, 2005, doi:10.1109/SFCS.2005.75

    1. Larkin, S. Sen, R. E. Tarjan, A back-to-basics empirical study of priority queues, Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX), 61-72, 2014, doi:10.1137/1.9781611973198.7

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes