ISRO2018-57

Question

Given a binary-max heap. The elements are stored in an arrays as $25, 14, 16, 13, 10, 8, 12$. What is the content of the array after two delete operations?

1. $14,13,8,12,10$
2. $14,12,13,10,8$
3. $14,13,12,8,10$
4. $14,13,12,10,8$

Comments

Here, binary max-heap is represented as an array whose elements are : 25,14,16,13,10,8,12.

 1) delete 25 :

first swap 25 and 12. So, array becomes : 12,14,16,13,10,8,25.

Now, delete 25 and decrease heap-size by 1. So, array becomes : 12,14,16,13,10,8

Now, apply max-heapify on it. So, array representation after max-heapify becomes : 16,14,12,13,10,8.

 2) delete 16 :

first swap 16 and 8. So, array becomes : 8,14,12,13,10,16.

Now, delete 16 and decrease heap-size by 1. So, array becomes : 8,14,12,13,10.

Now, apply max-heapify on it. So, array representation after max-heapify becomes : 14,13,12,8,10.

---

Yeah, I understood what you said but I am not able to digest it still.

you are directly swapping the values but the only way to do is heapify is what I know.

I still don't know what's wrong with the solution above which I have shown.

Can you please point out something there?

---

Problem is to apply heapify, we should have heap structure. You have deleted the root node which have element 25. Now, in heapify procedure, we should have 3 elements to compare :node, its left and right children, which have max/min, we make it as parent but here when we delete 25 then there is no key value for this node then how we will compare and how max-heapify procedure will work. That's why I said after deleting 25, we should have to shift all remaining elements to left in the array and then apply max-heapify.

Answer 1

max-heap deletion is always done at the root node.

• first, we delete a root node and call heapify.

Comments

@abhishekmehta4u

Why is that when you are deleting 16, the value 8 comes up to be the root (in the 4th step). Why doesn't 14 come up ??

In that case, we will be having a different answer...

---

@Satbir

Can you please explain this?

I am getting A as the answer

---

After delete 16 it is wrong.

if a root is deleted then, the child which has higher value becomes the root. so 14 should become root.

---

Right!

Answer 2

Initial array 25, 14, 16 13, 10, 8. 12
after first deletion array became : 16 ,14 , 12 , 13 , 10 , 8 and
after second deletion array became 14 , 13, 12, 8 , 10

So option C is correct.