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:
“Intolerance respecting other people’s religion is toleration itself in comparison with intolerance respecting other people’s art.”
—Wallace Stevens (1879–1955)
“What comes over a man, is it soul or mind
That to no limits and bounds he can stay confined?
You would say his ambition was to extend the reach
Clear to the Arctic of every living kind.
Why is his nature forever so hard to teach
That though there is no fixed line between wrong and right,
There are roughly zones whose laws must be obeyed?”
—Robert Frost (1874–1963)
“Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
—Eric Hoffer (1902–1983)