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:
“But the best read naturalist who lends an entire and devout attention to truth, will see that there remains much to learn of his relation to the world, and that it is not to be learned by any addition or subtraction or other comparison of known quantities, but is arrived at by untaught sallies of the spirit, by a continual self-recovery, and by entire humility.”
—Ralph Waldo Emerson (1803–1882)
“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)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)
“Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
—Eric Hoffer (1902–1983)