Difference between revisions of "Template:Heap Running Times"
Jump to navigation
Jump to search
imported>David Eppstein (edition= ?) |
(add a column with running time info for the 2-3 heap based on paper 'Theory of the 2-3 heap') |
||
| Line 42: | Line 42: | ||
| url = http://sidsen.org/papers/rp-heaps-journal.pdf}}</ref> | | url = http://sidsen.org/papers/rp-heaps-journal.pdf}}</ref> | ||
! [[Fibonacci heap|Strict Fibonacci]]<ref>{{Cite conference| doi = 10.1145/2213977.2214082| title = Strict Fibonacci heaps| conference = Proceedings of the 44th symposium on Theory of Computing - STOC '12| pages = 1177| year = 2012| last1 = Brodal | first1 = G. S. L. | last2 = Lagogiannis | first2 = G. | last3 = Tarjan | first3 = R. E. | isbn = 9781450312455| url = http://www.cs.au.dk/~gerth/papers/stoc12.pdf}}</ref> | ! [[Fibonacci heap|Strict Fibonacci]]<ref>{{Cite conference| doi = 10.1145/2213977.2214082| title = Strict Fibonacci heaps| conference = Proceedings of the 44th symposium on Theory of Computing - STOC '12| pages = 1177| year = 2012| last1 = Brodal | first1 = G. S. L. | last2 = Lagogiannis | first2 = G. | last3 = Tarjan | first3 = R. E. | isbn = 9781450312455| url = http://www.cs.au.dk/~gerth/papers/stoc12.pdf}}</ref> | ||
| + | ! [[2-3 heap]] | ||
|- | |- | ||
| find-min | | find-min | ||
| Line 52: | Line 53: | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
| + | |style="background:#ffffdd"| ''?'' | ||
|- | |- | ||
| delete-min | | delete-min | ||
| Line 62: | Line 64: | ||
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
|style="background:#ffffdd"| ''O''(log ''n'') | |style="background:#ffffdd"| ''O''(log ''n'') | ||
| + | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
|- | |- | ||
| insert | | insert | ||
| Line 72: | Line 75: | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
| + | |style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}} | ||
|- | |- | ||
| decrease-key | | decrease-key | ||
| Line 81: | Line 85: | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
| + | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|- | |- | ||
| Line 92: | Line 97: | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
| + | |style="background:#ffffdd"| ''?'' | ||
|} | |} | ||
{{notelist}} | {{notelist}} | ||
Revision as of 17:57, 16 August 2018
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][lower-alpha 1] | Rank-pairing[6] | Strict Fibonacci[7] | 2-3 heap |
|---|---|---|---|---|---|---|---|---|---|
| find-min | Θ(1) | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | ? |
| delete-min | Θ(log n) | Θ(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) | O(log n)[lower-alpha 2] |
| insert | O(log n) | Θ(log n) | Θ(1)[lower-alpha 2] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | O(log n)[lower-alpha 2] |
| decrease-key | Θ(log n) | Θ(n) | Θ(log n) | Θ(1)[lower-alpha 2] | o(log n)[lower-alpha 2][lower-alpha 3]).</math>[9]}} | Θ(1) | Θ(1)[lower-alpha 2] | Θ(1) | Θ(1) |
| merge | Θ(n) | Θ(log 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]
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 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.
- ↑ 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 (PDF), 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. (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.