GATE CS 2023 Q.46: Binary Heaps and Priority Queues

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, key) inserts a new element key 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?

Both Extract-Max(A) and Insert(A, key) run in $O(1)$ .

Both Extract-Max(A) and Insert(A, key) run in $O(\log(n))$ .

Extract-Max(A) runs in $O(1)$ and Insert(A, key) runs in $O(\log(n))$ .

Extract-Max(A) runs in $O(\log(n))$ and Insert(A, key) runs in $O(1)$ .

Official answer and solution

Official answer: B
From: Official GATE 2023 answer key

Solution

Recall standard worst-case time complexities of binary heap operations.

In a max-heap containing $n$ elements:

Extract-Max(A): The root contains the maximum element. Extracting it requires replacing the root with the last leaf and calling Max-Heapify, which traverses down the height of the tree. The tree height is $\lfloor \log_2 n \rfloor$ , so worst-case time is $O(\log n)$ .
Insert(A, key): Inserts the new element at the bottom-most leaf and bubbles it up toward the root to restore the max-heap property. Traversing up the tree height takes $O(\log n)$ in the worst case.

Thus, both operations run in $O(\log n)$ time.

Final answer

Option (B)

Common trap

Confusing Find-Max (which is $O(1)$ ) with Extract-Max (which deletes the maximum and requires $O(\log n)$ heapify).

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 46 of 65
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