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

@Shaik Masthan

Should the heap property be checked

Case – 1: After inserting each element

Case – 2: After the end of insertion of all elements

For the given question both cases give same answer.

Eg: Consider the following array of elements

$7,6,5,4,3,2,1$

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

Case 1 and 2 are giving different number of interchanges.

What should be the answer?

Case 1 or Case 2 or min(Case1, Case 2)?

---

Exactly same question asked before…

https://gateoverflow.in/2740

---

@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. 🙂

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