GATE CS 2016 Set 1 Q37 — Binary Heaps

To delete an element at the $i$-th index of a binary heap implemented as an array, we perform the following steps:

1. Replace the element at index $i$ with the last element of the heap (at index $n$).
2. Reduce the heap size by $1$.
3. Restore the heap property (re-fix the heap) at index $i$:
• If the replaced element is larger than its parent (in a max-heap), we bubble it up towards the root (heapify-up). This takes at most $O(d)$ time, where $d$ is the depth of the tree.
• If the replaced element is smaller than its children, we bubble it down towards the leaves (heapify-down). This also takes at most $O(d)$ time.

Thus, the overall time complexity to re-fix the heap is bounded by the depth of the tree, which is $O(d)$.

Why it is not $O(1)$:
In the worst case (for example, when we delete the root element), the replacement element must be bubbled down all the way to a leaf node. This requires traversing a path of length $d$, taking $\Theta(d)$ operations. Therefore, the time complexity is $O(d)$ but not $O(1)$.