Discussion
Minimum number of interchanges needed to convert the array 89,19,40,14,17,12,10,2,5,7,11,6,9,70, into a heap with the maximum element at the root is
Answer: B
Correct answer: 2
Build the max-heap bottom-up, checking each internal node from the last one back to the root. Numbering the array from 1:
1:89 2:19 3:40 4:14 5:17 6:12 7:10 8:2 9:5 10:7 11:11 12:6 13:9 14:70
- Node 7 holds 10 with the single child 70 - swap. Node 7 now holds 70.
- Nodes 6, 5 and 4 already dominate their children (12 over 6 and 9; 17 over 7 and 11; 14 over 2 and 5).
- Node 3 holds 40 with children 12 and 70 - swap with 70. The 40 that sinks to node 7 still beats its only child, 10.
- Node 2 (19 over 14 and 17) and the root (89 over 19 and 70) are already correct.
That is 2 interchanges in all.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development