Jump to content

User:IntGrah/Rank-pairing heap

From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Rank-pairing heap
Typeheap
Invented2011
Invented byBernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan
Complexities in big O notation
Space complexity
Space O(n)
Time complexity
Function Amortized Worst case
Insert Θ(1)
Find-min Θ(1)
Delete-min O(log n)
Decrease-key Θ(1)
Merge Θ(1)

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

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

Merge

Insert

Find-min

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

Decrease-key

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

Here are time complexities[2] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.

Operation find-min delete-min decrease-key insert meld make-heap[a]
Binary[2] Θ(1) Θ(log n) Θ(log n) Θ(log n) Θ(n) Θ(n)
Skew[3] Θ(1) O(log n) am. O(log n) am. O(log n) am. O(log n) am. Θ(n) am.
Leftist[4] Θ(1) Θ(log n) Θ(log n) Θ(log n) Θ(log n) Θ(n)
Binomial[2][6] Θ(1) Θ(log n) Θ(log n) Θ(1) am. Θ(log n)[b] Θ(n)
Skew binomial[7] Θ(1) Θ(log n) Θ(log n) Θ(1) Θ(log n)[b] Θ(n)
2–3 heap[9] Θ(1) O(log n) am. Θ(1) Θ(1) am. O(log n)[b] Θ(n)
Bottom-up skew[3] Θ(1) O(log n) am. O(log n) am. Θ(1) am. Θ(1) am. Θ(n) am.
Pairing[10] Θ(1) O(log n) am. o(log n) am.[c] Θ(1) Θ(1) Θ(n)
Rank-pairing[13] Θ(1) O(log n) am. Θ(1) am. Θ(1) Θ(1) Θ(n)
Fibonacci[2][14] Θ(1) O(log n) am. Θ(1) am. Θ(1) Θ(1) Θ(n)
Strict Fibonacci[15][d] Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(n)
Brodal[16][d] Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(n)[17]
  1. ^ make-heap is the operation of building a heap from a sequence of n unsorted elements. It can be done in Θ(n) time whenever meld runs in O(log n) time (where both complexities can be amortized).[3][4] Another algorithm achieves Θ(n) for binary heaps.[5]
  2. ^ a b c For persistent heaps (not supporting decrease-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-min is the sum of the old costs of delete-min and meld.[8] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-min still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.[7]
  3. ^ Lower bound of [11] upper bound of [12]
  4. ^ a b Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that decrease-key is not supported.

References

  1. ^ 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.
  2. ^ 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.
  3. ^ a b c Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing. 15 (1): 52–69. CiteSeerX 10.1.1.93.6678. doi:10.1137/0215004. ISSN 0097-5397.
  4. ^ a b Tarjan, Robert (1983). "3.3. Leftist heaps". Data Structures and Network Algorithms. pp. 38–42. doi:10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
  5. ^ Hayward, Ryan; McDiarmid, Colin (1991). "Average Case Analysis of Heap Building by Repeated Insertion" (PDF). J. Algorithms. 12: 126–153. CiteSeerX 10.1.1.353.7888. doi:10.1016/0196-6774(91)90027-v. Archived from the original (PDF) on 2016-02-05. Retrieved 2016-01-28.
  6. ^ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
  7. ^ a b 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
  8. ^ Okasaki, Chris (1998). "10.2. Structural Abstraction". Purely Functional Data Structures (1st ed.). pp. 158–162. ISBN 9780521631242.
  9. ^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
  10. ^ 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
  11. ^ 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.
  12. ^ 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.
  13. ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  14. ^ 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.
  15. ^ 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.
  16. ^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  17. ^ 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:IntGrah/Rank-pairing_heap&oldid=1255446735"