Template:Heap Running Times
From HandWiki
Revision as of 14:55, 9 April 2020 by imported>Jworkorg (1 revision imported)
Here are time complexities[1] 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[1] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
| Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
| Binomial[1][2] | Θ(1) | Θ(log n) | Θ(1)[lower-alpha 1] | Θ(log n) | O(log n)[lower-alpha 2] |
| Fibonacci[1][3] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
| Pairing[4] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | o(log n)[lower-alpha 1][lower-alpha 3] | Θ(1) |
| Brodal[7][lower-alpha 4] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| Rank-pairing[9] | Θ(1) | O(log n)[lower-alpha 1] | Θ(1) | Θ(1)[lower-alpha 1] | Θ(1) |
| Strict Fibonacci[10] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| 2-3 heap[11] | O(log n) | O(log n)[lower-alpha 1] | O(log n)[lower-alpha 1] | Θ(1) | ? |
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Amortized time.
- ↑ n is the size of the larger heap.
- ↑ Lower bound of [math]\displaystyle{ \Omega(\log\log n), }[/math][5] upper bound of [math]\displaystyle{ O(2^{2\sqrt{\log\log n}}). }[/math][6]
- ↑ 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).[8]
- ↑ 1.0 1.1 1.2 1.3 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" (in en-us). https://brilliant.org/wiki/binomial-heap/.
- ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery 34 (3): 596-615. doi:10.1145/28869.28874. http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf.
- ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2, http://john2.poly.edu/papers/swat00/paper.pdf
- ↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures". Journal of the Association for Computing Machinery 46 (4): 473–501. doi:10.1145/320211.320214. http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf.
- ↑ Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps". FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0. http://web.eecs.umich.edu/~pettie/papers/focs05.pdf.
- ↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues", Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58, http://www.cs.au.dk/~gerth/papers/soda96.pdf
- ↑ 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.
- ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps". SIAM J. Computing 40 (6): 1463–1485. doi:10.1137/100785351. http://sidsen.org/papers/rp-heaps-journal.pdf.
- ↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). "Strict Fibonacci heaps". Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5. http://www.cs.au.dk/~gerth/papers/stoc12.pdf.
- ↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps, pp. 12, https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/2-3heaps.pdf
