Template:Heap Running Times

From blackwiki
Revision as of 03:26, 1 September 2014 by imported>Wingedsubmariner (Creating with text from "Comparison of theoretic bounds for variants" section of Heap)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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] O(log n)[lower-alpha 2] Θ(1) Θ(1)[lower-alpha 2] Θ(1)
merge Θ(n) O(log n)[lower-alpha 3] Θ(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 Amortized time.
  3. 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.