Template:Heap Running Times
Revision as of 03:26, 1 September 2014 by imported>Wingedsubmariner (Creating with text from "Comparison of theoretic bounds for variants" section of Heap)
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.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.