Time complexity of deleting a leaf from a binary heap

Question

What is the time complexity of deleting a leaf node from a heap?

I think if you don't know where the node is it would be log n as you have to find it.

But if you already knew where the node was it should be O(1) right? Since you can just remove it and you don't have to re-heap everything?

Answer 1

Remember that binary heaps have to be complete binary trees, so if you remove a leaf other than the last leaf you'll need to move something to take its place. One way to do this is to swap it with the last leaf, delete the last leaf, and then do a bubble-up step to make sure that the heap property still holds. Aside from the time of actually locating the leaf node to remove, this takes time O(log n).

Hope this helps!