GATE CSE 2023 | Question: 36

Question

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))$.

Comments

The way EXTRACT-MAX(A) works is → we swap the root node with the right most node in the last level or you can say the last index of the array which contains the heap. Then we apply heapify method on new root node. Heapify on any node can take atmost O(logn) in the worst case as we may have to bubble down to the last level(leaf nodes level) of the tree . so Extract-Max(A) will have O(logn) time complexity

as for the INSERT(A) → we insert the new node in the leaf nodes level and then we bubble up according to the value of the new node. we can bubble up and can reach up to the root node in the worst case. That will take O(height) of the tree which will be equal to O(logn) as heap is a complete binary tree

correct answer is B

here’s the picture how extract max works

---

“The properties of a max-heap are preserved at the end of each of these operations.”

Option -B 
Avg case for insert is O(1) and delete is O(log n)
Worst case both O(log n)

---

@GO Classes@Lakshman Bhaiya In this question it's clearly mentioned that "...to insert a NEW element". BUT if we consider a general case, since it's a set of elements, we would have to find the element which takes O(n) time and if not found, insert the element which takes O(logn) time. So in that case time complexity of insertion would be O(n) not O(logn). Is this reasoning correct?

Answer 1

Priority Queue containing n elements is implemented using Max-Heap.

We are also provided with 2 operations : EXTRACT-MAX(A) & INSERT(A,key).

EXTRACT-MAX(A) extracts maximum element and delete it. 

Whereas, INSERT(A,key) inserts an element key in A.

 

Lets, start with considering INSERT(A,key) : If any key is inserted in max-heap, then it will be inserted at the last level. 

To create the worst case scenario, let’s suppose that newly inserted key is the greatest element among all,

that are present in the max-heap. In this scenario, the newly inserted element will go to the top

i.e. the height of the max-heap which is nothing but O(logn).

So, in worst case, the INSERT(A,key) will take O(log(n)).

 

With this conclusion Option A & C gets eliminated, because option A is saying Insert(A,key) will take O(1) &

option C is saying Insert(A,key) will take O(n).

 

Now, we are left with option B & option D.

 

Now, let’s consider EXTRACT-MAX(A) : As A is a mex-heap. So, maximum element is present at the

root itself. 

To extract the maximum element the root node element is swapped with the last element & then the

maximum element can easily be extracted. This swapping operation can be done in O(1).

But in question it is mentioned that “The properties of a max-heap are preserved at the end of each of these operations.”

Means, after swapping, we have to call Max-Heapify(A,1) function to maintain the properties of max-heap.

This operation will take O(logn). 

Overall time will be : O(1 + logn) = O(logn).

So, in this case also, EXTRACT-MAX(A) will take O(log(n)).

And, Option D is saying EXTRACT-MAX(A) can be done in O(1). So, option D is also rejected.

 

Now, we are only left with one option, option B, which is the correct answer. 

Both EXTRACT-MAX(A) & INSERT(A,key) run in O(log(n)). 

Answer 2

Both $\operatorname{Extract-Max}(A)$ and $\operatorname{Insert}(A)$ needs to perform $\operatorname{Heapify}()$ operation which takes $O(\log (n))$ time.

 

Hence, answer is B.

Answer 3

So , Both Extract – Max(A) and Insert(A) takes O(logn) time. 

Answer B