GATE CSE 2009 | Question: 60

Question

Consider a binary max-heap implemented using an array.
What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$

• A. $\left\{14,13,12,10, 8\right\}$
• B. $\left\{14,12,13,8,10\right\}$
• C. $\left\{14,13,8,12,10\right\}$
• D. $\left\{14,13,12,8,10\right\}$

Comments

i think @jeets is taking about removing the first element from the max-heap $ \ i.e \ ( A[0] )\ $and then incrementing the first index and doing the build-heap from $A[1 \ to \ n]$

then we will have to modify the code according to the index for the left and right index which will incur extra cost, which may increase the time complexity and result in different max heap tree.

i might be wrong, please do correct my understanding

---

@Amjad. I think @jeets is saying we delete the two highest elements in the array {25,14,16,13,10,8,12} i.e delete 25 and 16 and then build the max heap using the remaining array {14,13,10,8,12} which is itself a max heap but is very different from the options provided.

---

yeah , my concept was wrong , as per my concept all options would have been correct ,

this image represents the correct steps

Answer 1

During delete, the root element is removed, replaced with the last element and heap property is corrected by pushing the root downwards. So, for first delete,

$25 \ 14 \ 16 \ 13 \ 10 \ 8 \ 12 \rightarrow 12 \ 14 \ 16 \ 13 \ 10 \ 8 \rightarrow 16 \ 14 \ 12 \ 13 \ 10 \ 8$ (the element not satisfying max-heap property is exchanged with the largest of its children) (heap property satisfied)

Second delete:

$16 \ 14 \  12 \ 13 \ 10 \ 8 \rightarrow  8 \ 14 \ 12 \ 13 \ 10  \rightarrow  14 \  8  \ 12  \ 13  \ 10 \rightarrow  14 \ 13 \ 12 \ 8  \ 10$  (heap property satisfied)

Correct Answer: $D$

Comments

Why 25 was deleted first?

---

@parthivajith241 Because it’s a max-heap, the root i.e. 25 here is  the largest element. In a delete operation, we always remove the root first and then replaces it with the last element.

Answer 2

Answer is  :  [D] {14,13,12,,8,10}

Comments

Thnx

Answer 3

option d