GATE CS 2016 Set 1 Q.47 (CS Q.37): Binary Heaps and Priority Queues

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the $i$ -th node. Assume that the heap is implemented in an array and $i$ refers to the $i$ -th index of the array. If the heap tree has depth $d$ (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

$O(1)$

$O(d)$ but not $O(1)$

$O(2^d)$ but not $O(d)$

$O(d 2^d)$ but not $O(2^d)$

Official answer and solution

Official answer: B
From: Official GATE 2016 answer key

Solution

Analyze the heap deletion algorithm by swapping with the last leaf and applying heapify.

In a binary heap of depth $d$ stored in an array, deleting the item at index $i$ is performed as follows:

Replace the element at index $i$ with the last element of the heap (the rightmost leaf at the bottom level).
Decrease the heap size by 1.

The newly placed element may violate the heap ordering property in one of two directions:
- If the element is smaller (in a max-heap) than its parent, it must bubble down using heapify-down (or sift-down). In the worst case, it traverses a path down to a leaf, taking at most $O(d)$ comparisons and swaps.
- If the element is larger (in a max-heap) than its parent, it must bubble up using heapify-up (or sift-up). In the worst case, it traverses a path up to the root, taking at most $O(d)$ comparisons and swaps.

In either case, restoring the heap property takes at most $O(d)$ time. Since it requires traversing tree levels and cannot be done in $O(1)$ time in the worst case, the time complexity is $O(d)$ but not $O(1)$ .

Final answer

Common trap

Confusing the number of tree levels $d$ with the number of nodes $N = 2^{d+1} - 1$ , which would give $O(2^d)$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 47 of 65, printed as CS Q.37
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source