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:
“I have travelled a good deal in Concord; and everywhere, in shops, and offices, and fields, the inhabitants have appeared to me to be doing penance in a thousand remarkable ways.... The twelve labors of Hercules were trifling in comparison with those which my neighbors have undertaken; for they were only twelve, and had an end; but I could never see that these men slew or captured any monster or finished any labor.”
—Henry David Thoreau (1817–1862)
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)
“Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
—Eric Hoffer (1902–1983)