GATE CSE 1996 | Question: 2.11

Question

The minimum number of interchanges needed to convert the array into a max-heap is

$89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$

• A. $0$
• B. $1$
• C. $2$
• D. $3$

Comments

https://youtu.be/E1T3VQp4wGY?si=V9m2zhb2Qo2pqcIm this is a similar problem .

Answer 1

"The minimum number of interchanges needed to convert the array
$89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$
into a heap with the maximum element at the root node is:"

This is the correction.

Answer: C.

Only element $70$ violates the rule. Hence, it must be shifted to its proper position.
Step1: $swap(10, 70)$
Step2: $swap(40, 70)$
Hence, only $2$ interchanges are required.

Comments

@Jeet i think no of comparisons will be much more as heap sort will apply max heapify until the ROOT (that is from all Non leaves until the Root.

---

if the sequence is 89,19,40,17,12,10,2,5,7,11,6,9,70,90 than what would be the answer?

---

@Deepakk Poonia (Dee)

For example, in this question we could have also done the following :

Step1: swap(19,70)
Step2: swap(10,19)
Hence, only 2 interchanges are required

I couldn’t understand how you got Step $1$ and $2$. Could you give more explanation?

89,19,40,17,12,25,2,5,7,11,6,9,70

Try the same question for this array.

Answer will be 1 as we can just interchange 19 and 70, and we'll get max-heap.

Am getting a minimum of $2$ interchanges Swap$(25,70)$, Swap$(40,70)$.

Could you explain how you got only $1$ interchange?

Answer 2

2 interchanging is required.

Comments

nice explanation abhishek

---

How left side part is correct ?

Left side element of 19 is 17and right side element is 12 then they why they not interchange??

---

This should be the best answer...

---

@Akshaydd1 in max heap we need the the root element at every subtree to be maximum .

Answer 3

To get minimum number of exchanges ,just apply heapify function on each of the non leaf node starting from the last non leaf node and proceeding up the tree towards the root.In doing so,we encounter two interchanges 

Swap(70,10)

Swap(40,70)

Therefore,minimum number of interchanges needed are 2.