GATE CS 2015 Set 3 — Question 30
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+1 / -0.33MediumHeapify & Build-HeapHeapsProgramming & Data Structures
Programming & Data Structures → Heaps → Heapify & Build-Heap
Last updated
Question
Consider the following array of elements.
(89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100)
The minimum number of interchanges needed to convert it into a max-heap is
(89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100)
The minimum number of interchanges needed to convert it into a max-heap is
Correct answer
(D) 3
Solution
To convert an array into a max-heap, we use the
Number of elements .In a 0-indexed array, the parent of node is , and children are and .
The last non-leaf node is at index .
We will call
An interchange (swap) counts as one operation.Initial array (tree representation):
1.
Total minimum interchanges needed: 3.Therefore, the correct option is (D).
build_max_heap algorithm, which involves calling max_heapify on all non-leaf nodes, starting from the last non-leaf node up to the root.Given array: Number of elements .In a 0-indexed array, the parent of node is , and children are and .
The last non-leaf node is at index .
We will call
max_heapify for indices .An interchange (swap) counts as one operation.Initial array (tree representation):
89 (0)
/ \
19 (1) 50 (2)
/ \ / \
17(3) 12(4) 15(5) 2(6)
/ \ / \ / \
5(7) 7(8) 11(9) 6(10) 9(11) 100(12)
max_heapify(A, 5) (element 15):- Node 5 (15) has children 11 (9) and 12 (100).
- Max child is 100. . Swap and .
- Array:
- Interchanges: 1
max_heapify(A, 4) (element 12):- Node 4 (12) has children 9 (11) and 10 (6).
- Max child is 11. . No swap needed.
- Interchanges: 1 (total)
max_heapify(A, 3) (element 17):- Node 3 (17) has children 7 (5) and 8 (7).
- Max child is 7. . No swap needed.
- Interchanges: 1 (total)
max_heapify(A, 2) (element 50):- Node 2 (50) has children 5 (100) and 6 (2).
- Max child is 100. . Swap and .
- Array:
- Interchanges: 2
- Node 5 (50) now has children 11 (9) and 12 (15). and . No further swap for 50.
max_heapify(A, 1) (element 19):- Node 1 (19) has children 3 (17) and 4 (12).
- Max child is 17. . No swap needed.
- Interchanges: 2 (total)
max_heapify(A, 0) (element 89):- Node 0 (89) has children 1 (19) and 2 (100).
- Max child is 100. . Swap and .
- Array:
- Interchanges: 3
- Node 2 (89) now has children 5 (50) and 6 (2). and . No further swap for 89.
Total minimum interchanges needed: 3.Therefore, the correct option is (D).
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Heaps
2026 Set 2 Q12The set T represents various traversals over binary tree. The set S represents the order of…2026 Set 2 Q19Consider the following three ANSI-C programs, P1, P2, and P3. P1 [code] P2 [code] **P3**…2026 Set 1 Q23Let be an odd number greater than 100. Consider a binary minheap with elements stored in an…2026 Set 1 Q24Consider a hash table that is initially empty. The hash table is maintained…2026 Set 1 Q27Consider the following C statements: Which of the following options is/are correct? [figure]