Difference between revisions of "Template:Heap Running Times"
Jump to navigation
Jump to search
imported>Wingedsubmariner (Include correct information from Fibonacci heap) |
imported>Wingedsubmariner (Include reference) |
||
| Line 64: | Line 64: | ||
|style="background:#ffffdd"| ''Θ''(log ''n'') | |style="background:#ffffdd"| ''Θ''(log ''n'') | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
| − | |style="background:#ffffdd"| Unknown{{efn|name=pairingdecreasekey|Bounded by <math>\Omega(\log\log n) and {O(2^{2\sqrt{\log\log n}})}</math> | + | |style="background:#ffffdd"| Unknown{{efn|name=pairingdecreasekey|Bounded by <math>\Omega(\log\log n) and {O(2^{2\sqrt{\log\log n}})}</math><ref name="Fredman And Tarjan">{{cite journal|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan |title=Fibonacci heaps and their uses in improved network optimization algorithms| url = http://www.cl.cam.ac.uk/~sos22/supervise/dsaa/fib_heaps.pdf | format = PDF |journal=[[Journal of the Association for Computing Machinery]]|volume=34|year=1987|pages=596–615|ref=harv|doi=10.1145/28869.28874|issue=3}}</ref><ref>{{cite journal|last=Pettie|first=Seth|title=Towards a Final Analysis of Pairing Heaps|journal=Max Planck Institut für Informatik|year=2005|url=http://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}} |
|style="background:#ddffdd"| ''Θ''(1) | |style="background:#ddffdd"| ''Θ''(1) | ||
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | |style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}} | ||
Revision as of 03:45, 1 September 2014
The following time complexities[1] are amortized (worst-time) time complexity for entries marked by an asterisk, and regular worst case time complexities for all other entries. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see Big O notation). Function names assume a min-heap.
| Operation | Binary[1] | Binomial[1] | Fibonacci[1] | Pairing[2] | Brodal[3][lower-alpha 1] | Rank-pairing[5] | Strict Fibonacci[6] |
|---|---|---|---|---|---|---|---|
| find-min | Θ(1) | Θ(1) | Θ(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 | Θ(log n) | O(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| decrease-key | Θ(log n) | Θ(log n) | Θ(1)[lower-alpha 2] | Unknown[lower-alpha 3])}</math>[7][8]}} | Θ(1) | Θ(1)[lower-alpha 2] | Θ(1) |
| merge | Θ(m log(n+m))[lower-alpha 4] | O(log n)[lower-alpha 5] | Θ(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).[4]
- ↑ 2.0 2.1 2.2 2.3 2.4 Amortized time.
- ↑ Bounded by <math>\Omega(\log\log n) and {O(2^{2\sqrt{\log\log n
- ↑ n is the size of the larger heap and m is the size of the smaller heap.
- ↑ n is the size of the larger heap.
- ↑ 1.0 1.1 1.2 1.3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.
- ↑ 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
- ↑ 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.
- ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2009). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485.
- ↑ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/2213977.2214082, please use {{cite journal}} with
|doi=10.1145/2213977.2214082instead. - ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (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)
- ↑ Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps" (PDF). Max Planck Institut für Informatik.