Template:Heap Running Times

From blackwiki
Revision as of 03:45, 1 September 2014 by imported>Wingedsubmariner (Include reference)
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] 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. 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.