0

I've been told that the best case time complexity of deleting an element from a max heap is O(1).

From what I understand, the best case should be O(logn) since we always have to perculate down after deleting the root and placing the last eleement in the heap at the root.

Then the question is - how could the best case be O(1)

Thanks in advance

Yoav Rosenbaum
  • 3
  • 1
  • 2

1 Answers1

3

I am assuming you are talking about a binary heap, here is a simple case that shows the best case behavior.

Assume a binary heap of all identical elements.

Deletion from the binary heap is first switching the head with the last child, removing this child, and then making adjustments to ensure it is still a heap.

But in our case, after switching the head with the last element we still have root.value >= root.left.value && root.value >= root.right.value, so we are done.

For this case, the number of operations is constant (regardless of the heap's size), so we can conclude this case is O(1), and since the best case cannot be better than O(1) (there is no algorithm that runs better than that, in terms of asymptotic notation), we can conclude that the best case is O(1) (tight bound).

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • The binary heap doesn't have to contain all identical elements (err... rather equivalent key values) to have the last element remain root. The actual condition is that all its ancestors are equal to its value. The other elements in the max heap may be smaller. – gen-y-s Jul 03 '15 at 17:10
  • @gen-y-s To show something is "Best case" (or equivalently "worst case") you just need to show a single example, there is no need t generalize it as much as possible, so I didn't bother. – amit Jul 03 '15 at 17:11
  • And there are many more cases, where only a few moves down would be required. For example, if the last child is smaller than all its own ancestor, and the root's other child is second largest in the heap, but its subtree items are all smaller than the last child. In this case the last child will be moved to root position, and switched with the larger child, and thats it. This is also O(1). – gen-y-s Jul 03 '15 at 17:15
  • @gen-y-s I don't get where you're heading, I am not trying to list all the possibilities where `O(1)` extraction happens, just aimed to show a single example. – amit Jul 03 '15 at 17:17