GATE CSE 2015 | Set 3 | Question: 19

Question

Consider the following array of elements.

$\langle 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 \rangle$

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

• A. $4$
• B. $5$
• C. $2$
• D. $3$

Comments

@ASNR1010 bro are you making collection of repeated questions??

---

Nopes bro, I just put the links of whatever question I found repeated. So any future aspirant can see the resemblance. 🙂

---

100 needs to be swapped with 15 then with 50 then with 89 => 3 swaps

Answer 1

Interchanges:

• 1$^{\text{st}}$ $15$-$100$
• 2$^{\text{nd}}$ $50$-$100$
• 3$^{\text{rd}}$ $89$-$100$

Total interchange $3$ so option (D) is correct.

Answer 2

3 swaps needed

Answer 3

We can use Build Heap or Insertion method to convert given array into max heap . In both case 3 swaps are required .

Swap(100,15)

Swap(50,100)

Swap(89,100)

So option D is correct ans.

Comments

14 i think.

---

How to count the no of comparisons

---

@Sambhrant Maurya

Have you counted 2 comparisons for each element from top to bottom?

Answer 4

3  interchanges needed to convert it into a max-heap