Difference between revisions of "Template:Heap Running Times"

From blackwiki
Jump to navigation Jump to search
(double quotes dont make italics)
(tweak big Os so theyre consistent)
Line 42: Line 42:
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized|Amortized time.}}
+
|style="background:#ffffdd"| ''Θ''(log ''n''){{efn|name=amortized|Amortized time.}}
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
+
|style="background:#ffffdd"| ''Θ''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
+
|style="background:#ffffdd"| ''Θ''(log ''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=amortized}}
+
|style="background:#ffffdd"| ''Θ''(log ''n''){{efn|name=amortized}}
|style="background:#ffffdd"| ''O''(log ''n'')
+
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|-
 
|-
 
| insert
 
| insert
|style="background:#ffffdd"| ''O''(log ''n'')
+
|style="background:#ffffdd"| ''Θ''(log ''n'')
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
|style="background:#ddffdd"| ''Θ''(1){{efn|name=amortized}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
Line 61: Line 61:
 
|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"| ''o''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|Bounded by <math>\Omega(\log\log n), 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&ndash;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&uuml;r Informatik|year=2005|url=http://web.eecs.umich.edu/~pettie/papers/focs05.pdf}}</ref>}}
+
|style="background:#ffffdd"| ''Θ''(log ''n''){{efn|name=amortized}}{{efn|name=pairingdecreasekey|Bounded by <math>\Omega(\log\log n), 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&ndash;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&uuml;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}}
Line 68: Line 68:
 
| merge
 
| merge
 
|style="background:#ffdddd"| ''Θ''(''n'')
 
|style="background:#ffdddd"| ''Θ''(''n'')
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
+
|style="background:#ffffdd"| ''Θ''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)

Revision as of 12:02, 19 September 2016

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] Pairing[2] Brodal[3][lower-alpha 1] Rank-pairing[5] Strict Fibonacci[6]
find-min Θ(1) Θ(log n) Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
delete-min Θ(log n) Θ(log n) Θ(log n)[lower-alpha 2] Θ(log n)[lower-alpha 2] Θ(log n) Θ(log n)[lower-alpha 2] Θ(log n)
insert Θ(log n) Θ(1)[lower-alpha 2] Θ(1) Θ(1) Θ(1) Θ(1) Θ(1)
decrease-key Θ(log n) Θ(log n) Θ(1)[lower-alpha 2] Θ(log n)[lower-alpha 2][lower-alpha 3])</math>[7][8]}} Θ(1) Θ(1)[lower-alpha 2] Θ(1)
merge Θ(n) Θ(log n)[lower-alpha 4] Θ(1) Θ(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. 2.0 2.1 2.2 2.3 2.4 2.5 2.6 Amortized time.
  3. Bounded by <math>\Omega(\log\log n), O(2^{2\sqrt{\log\log n
  4. n is the size of the larger heap.
  1. 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.
  2. 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
  3. Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues", Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 52–58
  4. Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341.
  5. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2009). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485.
  6. 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.
  7. 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)
  8. Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps" (PDF). Max Planck Institut für Informatik.