GATEverse — GATE CSE previous year questions

Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $\text{EXTRACT-MAX} (A)$ extracts and deletes the maximum element from $A$ . The operation $\operatorname{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 $\text{TRUE}?$

(A)

Both $\text{EXTRACT-MAX} (A)$ and $\operatorname{INSERT}(A, k e y)$ run in $O(1)$ .

(B)

Both $\text{EXTRACT-MAX} (A)$ and $\operatorname{INSERT}(A, k e y)$ run in $O(\log (n))$ .

(C)

$\text{EXTRACT-MAX} (A)$ runs in $O(1)$ whereas $\operatorname{INSERT}(A, k e y)$ runs in $O(n)$ .

(D)

$\text{EXTRACT-MAX} (A)$ runs in $O(1)$ whereas $\operatorname{INSERT}(A, k e y)$ runs in $O(\log (n))$ .