Template:Heap Running Times
Revision as of 09:01, 29 December 2016 by 71.41.210.146 (talk) (Fixed dead link, moved wrong Fredman paper to Fibonacci heap column where it belongs, insert right Fredman paper in pairing heap bounds footnote, other reference maintenance.)
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] | Binomial[1] | Fibonacci[1][2] | Pairing[3] | Brodal[4][lower-alpha 1] | Rank-pairing[6] | Strict Fibonacci[7] |
---|---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
delete-min | Θ(log n) | Θ(log n) | O(log n)[lower-alpha 2] | O(log n)[lower-alpha 2] | O(log n) | O(log n)[lower-alpha 2] | O(log n) |
insert | O(log n) | Θ(1)[lower-alpha 2] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
decrease-key | Θ(log n) | Θ(log n) | Θ(1)[lower-alpha 2] | o(log n)[lower-alpha 2][lower-alpha 3]).</math>[9]}} | Θ(1) | Θ(1)[lower-alpha 2] | Θ(1) |
merge | Θ(n) | O(log n)[lower-alpha 4] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
- ↑ 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).[5]
- ↑ Jump up to: 2.0 2.1 2.2 2.3 2.4 2.5 2.6 Amortized time.
- ↑ Lower bound of <math>\Omega(\log\log n),</math>[8] upper bound of <math>O(2^{2\sqrt{\log\log n
- ↑ n is the size of the larger heap.
- ↑ Jump up to: 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.
- ↑ 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.CS1 maint: ref=harv (link)
- ↑ 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, 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. (2009). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485.
- ↑ 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.