Comparison of Theoretic Bounds For Variants
The following time complexities 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 | Binomial | Fibonacci | Pairing | Brodal*** | RP |
|---|---|---|---|---|---|---|
| find-min | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| delete-min | Θ(log n) | Θ(log n) | O(log n)* | O(log n)* | O(log n) | O(log n)* |
| insert | Θ(log n) | O(log n) | Θ(1) | Θ(1)* | Θ(1) | Θ(1) |
| decrease-key | Θ(log n) | Θ(log n) | Θ(1)* | O(log n)* | Θ(1) | Θ(1)* |
| merge | Θ(n) | O(log n)** | Θ(1) | Θ(1)* | Θ(1) | Θ(1) |
(*)Amortized time
(**)Where n is the size of the larger heap
(***)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).
Read more about this topic: Heap (data Structure)
Famous quotes containing the words comparison, bounds and/or variants:
“The comparison between Coleridge and Johnson is obvious in so far as each held sway chiefly by the power of his tongue. The difference between their methods is so marked that it is tempting, but also unnecessary, to judge one to be inferior to the other. Johnson was robust, combative, and concrete; Coleridge was the opposite. The contrast was perhaps in his mind when he said of Johnson: “his bow-wow manner must have had a good deal to do with the effect produced.””
—Virginia Woolf (1882–1941)
“Great Wits are sure to Madness near alli’d
And thin Partitions do their Bounds divide;
Else, why should he, with Wealth and Honour blest,
Refuse his Age the needful hours of Rest?”
—John Dryden (1631–1700)
“Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
—Eric Hoffer (1902–1983)