retagged by
6,071 views
7 votes
7 votes

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}?$

  1. Both $\text{EXTRACT-MAX} (A)$ and $\operatorname{INSERT}(A, k e y)$ run in $O(1)$.
  2. Both $\text{EXTRACT-MAX} (A)$ and $\operatorname{INSERT}(A, k e y)$ run in $O(\log (n))$.
  3. $\text{EXTRACT-MAX} (A)$ runs in $O(1)$ whereas $\operatorname{INSERT}(A, k e y)$ runs in $O(n)$.
  4. $\text{EXTRACT-MAX} (A)$ runs in $O(1)$ whereas $\operatorname{INSERT}(A, k e y)$ runs in $O(\log (n))$.
retagged by

3 Answers

14 votes
14 votes

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

edited by
8 votes
8 votes

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.

1 votes
1 votes

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

Answer B

Answer: