Template talk:Heap Running Times

Theta versus big-O

Changed running time for decrease-key of binary heap from Theta(log n) to O(log n). This reflects the fact that decrease-key may terminate after a constant number of steps so is not tight-bounded by logn. This is probably true for other heaps as well. Alex Kindel (talk) 22:29, 16 December 2018 (UTC)

This reasoning is incorrect. The complexity function f(n) is the number of operations in the worst case. The fact that the number of operations may be constant in some lucky cases does not affect the number of operations in the worst case. The worst case does exhibit a logarithmic behavior, therefore f(n) ≥ a × log(n) + b for some constants a and b, therefore f(n) is asymptotically bounded below by log(n), which we note as f(n) = Ω(n); since it is also asymptotically bounded above by log(n), which we note as f(n) = O(n), we finally have f(n) = θ(n). Maëlan 03:30, 25 July 2024 (UTC)

Clarify average or worst-case time complexity

This is not clear from the template Wqwt (talk) 18:46, 20 July 2022 (UTC)

This really needs to be done to avoid confusion such as the discussion on "proof for O(1) average-case insertion" at https://en.wikipedia.org/wiki/Talk:Binary_heap, and note that this table contradicts what the Binary_heap page currently says.

Binary heaps are O(1) best and average time for insertion of a random value, and worst case O(ln N) when inserting a new min value. This table only has the worst-case and is miss-leading. I strongly suggest the table should include the average times, with citation links explaining what the best/worst case is if they are different. This is mostly what the table already does, but it is wrong for Binary heap insertion, and maybe some other heap types.

It would also be good to include an "increase-key" column as another fairly common operation. For Binary Heap this is O(1) on average, and worst case O(ln N) for increasing the min-value. DonovanBaarda (talk) 00:51, 5 September 2023 (UTC)

Is there too much in the footnotes?

@Maëlan Footnotes look too tall to me now; perhaps reduce the content about structural abstraction? Would you consider taking out the bit on Binary heaps, since "logarithmic meld" already implies that it doesn't apply to Binary heaps? IntGrah (talk) 23:34, 31 July 2024 (UTC)

Hi @IntGrah:, thanks for your contributions on this topic! I already tried my best for concision. I think the part about make-heap in binary heaps can be shortened a bit, but I’d prefer to keep some part of it, because otherwise an attentive reader might think it is a mistake from Wikipedia editors that make-heap for binary trees is said to be in O(n) (since the footnote now applies to the whole column).

On second thought, I would remove the very mention of the technique’s name—structural abstraction—since it is already found in the title of the book chapter cited as reference, and since the Brodal-Okasaki paper refers to it under a different (broader) name—datastructural bootstrapping. Will do.

Ideally, that footnote would clarify that the technique builds a new implementation (representation) of heaps from a given base implementation; it doesn’t simply add a new operation to the existing implementation; which is why the table only mentions the O(log n) complexity instead of the improved O(1). The datastructures that support meld in O(1) are not binomial heaps anymore, nor skew binomial heaps, and have larger constants factors than these (the transformation is more involved than just adding a root to store the minimum). But I could not find how to explain this with a satisfying amount of brevity and simplicity. Maëlan 19:15, 2 August 2024 (UTC)

I shortened the footnotes. Maëlan 12:45, 3 August 2024 (UTC)

Looks good to me. Thanks. IntGrah (talk) 14:24, 3 August 2024 (UTC)