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

Answer :. 14, 13 ,12 ,8, 10

None of the option is match

---

@Hradesh patel

small typo in option (c). corrected now.

---

I don't know why I am getting:

14 13 8 12 10 as my answer.

---

@`JEET 

 Can you tell me how you are getting 14,13,8,12,10.

Here, , in questiont is not given which 2 elements we have to delete in binary max-heap. I am assuming that we have to delete first 2 maximum elements one by one.

In max-heap or min-heap, to delete target element, first we have to swap, target element with last element and then delete the last element but in this procedure property of max-heap or min-heap may violate. So, we have to fix it by using max-heapify or min-heapify.

1) To delete 25,

-- first swap 25 with last element in the array i.e. 12

-- delete 25 

-- Apply max-heapify.

Then do the same procedure for next maximum element.

---

I have to maintain the heap property while deleting, right?

---

What is wrong in this @ankitgupta.1729

@Satbir

---

@`JEET if we delete 25, which is the 1st element in the array, like this way, we have to shift all the elements in the left to maintain the heap structure and decrease the heap-size by 1 then only we can apply max-heapify.. right ? and shifting all remaining elements will take worst case O(n) time. right ?

---

But it is not technically incorrect?

Can you please show your method?

---

Answers aren't helpful for this question.

---

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.