Template:Heap Running Times
In the following time complexities[1] O(f) is an asymptotic upper bound and Θ(f) is an asymptotically tight bound (see Big O notation). Function names assume a min-heap.
| Operation | Binary[1] | Leftist | Binomial[1] | Fibonacci[1][2] | Pairing[3] | Brodal[4][a] | Rank-pairing[6] | Strict Fibonacci[7] |
|---|---|---|---|---|---|---|---|---|
| find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| delete-min | Θ(log n) | Θ(log n) | Θ(log n) | O(log n)[b] | O(log n)[b] | O(log n) | O(log n)[b] | O(log n) |
| insert | O(log n) | Θ(log n) | Θ(1)[b] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| decrease-key | Θ(log n) | Θ(n) | Θ(log n) | Θ(1)[b] | o(log n)[b][c] | Θ(1) | Θ(1)[b] | Θ(1) |
| merge | Θ(n) | Θ(log n) | O(log n)[d] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
- ^ 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.
- ^ 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. doi:10.1145/28869.28874.
{{cite journal}}: Invalid|ref=harv(help) - ^ 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, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
- ^ 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.
- ^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485. doi:10.1137/100785351.
- ^ Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 9781450312455.
- ^ 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.