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 of, comparison, bounds and/or variants:
“We teach boys to be such men as we are. We do not teach them to aspire to be all they can. We do not give them a training as if we believed in their noble nature. We scarce educate their bodies. We do not train the eye and the hand. We exercise their understandings to the apprehension and comparison of some facts, to a skill in numbers, in words; we aim to make accountants, attorneys, engineers; but not to make able, earnest, great- hearted men.”
—Ralph Waldo Emerson (1803–1882)
“Intolerance respecting other people’s religion is toleration itself in comparison with intolerance respecting other people’s art.”
—Wallace Stevens (1879–1955)
“Firmness yclept in heroes, kings and seamen,
That is, when they succeed; but greatly blamed
As obstinacy, both in men and women,
Whene’er their triumph pales, or star is tamed —
And ‘twill perplex the casuist in morality
To fix the due bounds of this dangerous quality.”
—George Gordon Noel Byron (1788–1824)
“Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
—Eric Hoffer (1902–1983)