Difference between revisions of "Template:Heap Running Times"

From blackwiki
Jump to navigation Jump to search
imported>Wingedsubmariner
(Creating with text from "Comparison of theoretic bounds for variants" section of Heap)
 
imported>Wingedsubmariner
(Include correct information from Fibonacci heap)
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"| ''O''(log ''n''){{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>*<ref name="Fredman And Tarjan"/><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 70: Line 70:
 
|-
 
|-
 
| merge
 
| merge
|style="background:#ffdddd"| ''Θ''(''n'')
+
|style="background:#ffdddd"| ''Θ''(''m'' log(''n''+''m'')){{efn|name=merge2|''n'' is the size of the larger heap and ''m'' is the size of the smaller heap.}}
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
 
|style="background:#ffffdd"| ''O''(log ''n''){{efn|name=merge|''n'' is the size of the larger heap.}}
 
|style="background:#ddffdd"| ''Θ''(1)
 
|style="background:#ddffdd"| ''Θ''(1)

Revision as of 03:42, 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)
  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 Amortized time.
  3. Bounded by <math>\Omega(\log\log n) and {O(2^{2\sqrt{\log\log n
  4. n is the size of the larger heap and m is the size of the smaller heap.
  5. n is the size of the larger heap.
  1. 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.
  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. http://www.cs.au.dk/~gerth/papers/soda96.pdf
  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. 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.2214082 instead.
  7. Cite error: Invalid <ref> tag; no text was provided for refs named Fredman And Tarjan
  8. Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps" (PDF). Max Planck Institut für Informatik.