32 votes 32 votes 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 $4$ $5$ $2$ $3$ DS gatecse-2015-set3 data-structures heap easy + – go_editor asked Feb 14, 2015 retagged Dec 16, 2023 by Hira Thakur go_editor 8.9k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Shiva Sagar Rao commented Oct 28, 2020 reply Follow Share @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)? 2 votes 2 votes Kiyoshi commented Apr 30, 2021 reply Follow Share Exactly same question asked before… https://gateoverflow.in/2740 1 votes 1 votes abir_banerjee commented Jul 12, 2022 reply Follow Share @ASNR1010 bro are you making collection of repeated questions?? 0 votes 0 votes Kiyoshi commented Jul 12, 2022 reply Follow Share Nopes bro, I just put the links of whatever question I found repeated. So any future aspirant can see the resemblance. 🙂 4 votes 4 votes Please log in or register to add a comment.
Best answer 37 votes 37 votes Interchanges: 1$^{\text{st}}$ $15$-$100$ 2$^{\text{nd}}$ $50$-$100$ 3$^{\text{rd}}$ $89$-$100$ Total interchange $3$ so option (D) is correct. Anoop Sonkar answered Feb 15, 2015 edited Jan 17, 2023 by shadymademe Anoop Sonkar comment Share Follow See all 0 reply Please log in or register to add a comment.
11 votes 11 votes 3 swaps needed pankaj_vir answered Mar 24, 2018 pankaj_vir comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes 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. Rajesh Pradhan answered Aug 28, 2016 Rajesh Pradhan comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments adarsh_1997 commented Jul 27, 2019 reply Follow Share 14 i think. 0 votes 0 votes neel19 commented Jan 31, 2021 reply Follow Share How to count the no of comparisons 0 votes 0 votes Pranavpurkar commented Jul 24, 2022 reply Follow Share @Sambhrant Maurya Have you counted 2 comparisons for each element from top to bottom? 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes 3 interchanges needed to convert it into a max-heap Rohit01 answered Sep 20, 2015 Rohit01 comment Share Follow See all 0 reply Please log in or register to add a comment.