GATE 2023 CS Q.46: solution and answer

GATE 2023 · CSQ.46 · 2 marks · MCQ

Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $EXTRACT-MAX (A)$ extracts and deletes the maximum element from $A$ . The operation $INSERT (A, k ey)$ inserts a new element $k ey$ in $A$ . The properties of a max-heap are preserved at the end of each of these operations.

When $A$ contains $n$ elements, which one of the following statements about the worst case running time of these two operations is TRUE?

(A)
Both $EXTRACT-MAX (A)$ and $INSERT (A, k ey)$ run in $O (1)$ .
(B)
Both $EXTRACT-MAX (A)$ and $INSERT (A, k ey)$ run in $O (lo g (n))$ .
(C)
$EXTRACT-MAX (A)$ runs in $O (1)$ whereas $INSERT (A, k ey)$ runs in $O (n)$ .
(D)
$EXTRACT-MAX (A)$ runs in $O (1)$ whereas $INSERT (A, k ey)$ runs in $O (lo g (n))$ .

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (B) is TRUE: both EXTRACT-MAX(A) and INSERT(A, key) run in O(log(n)) in the worst case.

Official answer: BSource: Official answer key, GATE 2023 CS (IIT Kanpur)

A max-heap on $n$ elements is stored as a nearly complete binary tree of height $Θ (lo g (n))$ , kept in an array.
$INSERT (A, k ey)$ : place $k ey$ at the next free array position (a new leaf), then sift it up — repeatedly compare with its parent and swap while the max-heap property is violated. In the worst case the element travels from a leaf all the way to the root, giving $O (lo g (n))$ comparisons and swaps.
$EXTRACT-MAX (A)$ : the maximum sits at the root, so reading it is $O (1)$ . To remove it while keeping the tree complete, the LAST element in the array is moved into the root position and the heap size is decremented.
This relocated element is then sifted down (max-heapify): at each level it is compared with its larger child and swapped down if it violates the max-heap property, following a single root-to-leaf path.
Sifting down takes $O (lo g (n))$ comparisons and swaps in the worst case, since it can traverse the full height of the tree.
So $EXTRACT-MAX (A)$ costs $O (1)$ (locate the max) plus $O (lo g (n))$ (restore the heap) $= O (lo g (n))$ overall — the same asymptotic order as $INSERT (A, k ey)$ .
Hence both operations run in $O (lo g (n))$ worst-case time, so statement (B) is TRUE.

KEY IDEA

A binary (max-)heap stored as a nearly complete binary tree has height $Θ (lo g (n))$ ; both INSERT (sift-up from a new leaf) and EXTRACT-MAX (move last element to root, then sift-down/max-heapify) do work proportional to the tree's height, so both are $O (lo g (n))$ in the worst case — reading the max itself is $O (1)$ , but restoring the heap property after removing it is not.

WATCH OUT FOR

Assuming EXTRACT-MAX is $O (1)$ overall because "the maximum is right at the root" (options C/D) — this only covers locating/reading the max. Removing it still requires refilling the root (with the last array element) and sifting it down through up to $Θ (lo g (n))$ levels to restore the max-heap property, so the operation as a whole costs $O (lo g (n))$ , not $O (1)$ .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 26 Trees & heaps questions, with notes

GATE 2023 CS Q.46: solution and answer

Answer and solution

More Trees & heaps questions