Draft:Rank-pairing heap
| Rank-pairing heap | |||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | heap | ||||||||||||||||||||||||||||||||||||
| Invented | 2011 | ||||||||||||||||||||||||||||||||||||
| Invented by | Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan | ||||||||||||||||||||||||||||||||||||
| Complexities in big O notation | |||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||
In computer science, a rank-pairing heap is a data structure for priority queue operations. Rank-pairing heaps were designed to match the amortized running times of Fibonacci heaps whilst maintaining the simplicity of pairing heaps. Rank-pairing heaps were invented in 2011 by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan.[1]
Structure[edit]
A rank-pairing heap is a list of heap-ordered trees represented in the left-child right-sibling binary tree format. This means that each node has one pointer to its left-most child, and another pointer to its right sibling. Additionally, each node maintains a pointer to its parent.
Operations[edit]
Merge[edit]
Insert[edit]
Find-min[edit]
We maintain a pointer to the node containing the minimum key. This will always be a root within the list of trees. The minimum key can thus be found at a constant cost, with only a minor overhead in the other operations.
Delete-min[edit]
Decrease-key[edit]
To decrease the key of a node , reduce its key, and update the minimum key pointer, if it is the new minimum. Then, the subtree rooted at is detached; in the left-child right-sibling representation, this is equivalent to replacing with its right child . The detached subtree is added to the list of trees, and the ranks are recalculated: the rank of is set to be one greater than its left child, and the ancestors of have their ranks reduced.
Summary of running times[edit]
Here are time complexities[2] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
| Operation | find-min | delete-min | insert | decrease-key | meld |
|---|---|---|---|---|---|
| Binary[2] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
| Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
| Binomial[2][3] | Θ(1) | Θ(log n) | Θ(1)[a] | Θ(log n) | O(log n) |
| Skew binomial[4] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n)[b] |
| Pairing[5] | Θ(1) | O(log n)[a] | Θ(1) | o(log n)[a][c] | Θ(1) |
| Rank-pairing[8] | Θ(1) | O(log n)[a] | Θ(1) | Θ(1)[a] | Θ(1) |
| Fibonacci[2][9] | Θ(1) | O(log n)[a] | Θ(1) | Θ(1)[a] | Θ(1) |
| Strict Fibonacci[10] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| Brodal[11][d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| 2–3 heap[13] | Θ(1) | O(log n)[a] | Θ(1)[a] | Θ(1) | O(log n) |
- ^ a b c d e f g h i Amortized time.
- ^ Brodal and Okasaki describe a technique to reduce the worst-case complexity of meld to Θ(1); this technique applies to any heap datastructure that has insert in Θ(1) and find-min, delete-min, meld in O(log n).
- ^ Lower bound of [6] upper bound of [7]
- ^ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).[12]
References[edit]
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (Jan 2011). "Rank-Pairing Heaps". SIAM Journal on Computing. 40 (6): 1463–1485. doi:10.1137/100785351. ISSN 0097-5397.
- ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- ^ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
- ^ Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi:10.1017/s095679680000201x
- ^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
- ^ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
- ^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
- ^ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
- ^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
- ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
- ^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12