Template talk:Heap Running Times

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)

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)