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 binary-heap easy + – go_editor asked Feb 14, 2015 • retagged Dec 16, 2023 by Hira Thakur go_editor 9.1k 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 Thadymademe 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 Lakshman Bhaiya commented Feb 2, 2018 reply Follow Share In given question nothing mention about Build Heap or Insertion method to convert given array into the max heap. we can use any method to get the same answer?? 0 votes 0 votes Sambhrant Maurya commented Jul 25, 2019 reply Follow Share Is the no. of comparisons performed here 12? 0 votes 0 votes adarsh_1997 commented Jul 27, 2019 reply Follow Share @Sambhrant Maurya i think if we we r using build heap function then no of comparison will be 12 but in case of using insertion operation at every step i feel comparsion will be different. isint so? 0 votes 0 votes 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.