# Binary heaps: GATE CS question with solution

From the GATE Daily set of 26 October 2026, question 6 of 10 (https://gatedaily.in/q/2026-10-26-build-min-heap-bottom-up-final-array/). Difficulty: standard.

### Q.6 · Programming & Data Structures · Binary heaps · MCQ, 2 marks (choose one option)

The array $A[1..10]$ below is turned into a **min-heap** in place by the standard bottom-up build-heap procedure: for $i = \lfloor n/2 \rfloor$ down to $1$, sift $A[i]$ down, at each step swapping it with its smaller child as long as that child is smaller than it. The children of $A[i]$ are $A[2i]$ and $A[2i+1]$.

| Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Value | 45 | 12 | 78 | 33 | 9 | 60 | 21 | 5 | 40 | 18 |

Which one of the following is the array $A[1..10]$ after build-heap finishes?

(A) 5, 9, 21, 12, 18, 60, 78, 33, 40, 45
(B) 5, 9, 21, 12, 18, 78, 60, 45, 40, 33
(C) 5, 9, 21, 12, 45, 60, 78, 33, 40, 18
(D) 5, 9, 12, 18, 21, 33, 40, 45, 60, 78

**Answer:** (A) 5, 9, 21, 12, 18, 60, 78, 33, 40, 45

**Solution.** **Method: trace the sift-downs from the last internal node to the root.**

$n = 10$, so start at $i = 5$.

1. $i = 5$: $A[5] = 9$, child $A[10] = 18$. No swap.
2. $i = 4$: $A[4] = 33$, children 5 and 40. Swap with 5. Array: 45, 12, 78, **5**, 9, 60, 21, **33**, 40, 18.
3. $i = 3$: $A[3] = 78$, children 60 and 21. Swap with 21. Array: 45, 12, **21**, 5, 9, 60, **78**, 33, 40, 18.
4. $i = 2$: $A[2] = 12$, children 5 and 9. Swap with 5; at index 4, 12 has children 33 and 40, stop. Array: 45, **5**, 21, **12**, 9, 60, 78, 33, 40, 18.
5. $i = 1$: $A[1] = 45$, children 5 and 21. Swap with 5. At index 2, children 12 and 9: swap with 9. At index 5, child 18: swap. Array: **5**, **9**, 21, 12, **18**, 60, 78, 33, 40, **45**.

Final: 5, 9, 21, 12, 18, 60, 78, 33, 40, 45 (6 swaps in all).

**Trap.** Options (b) and (d) are also valid min-heaps. A question about a *procedure* is answered by tracing that procedure, not by checking the heap property. Inserting keys one at a time builds a different heap from the same keys. And a sift-down continues until the key is no larger than both children, which can take it several levels (45 travels from index 1 to index 10).

**What was tested:** executing bottom-up build-heap exactly, including sift-downs that continue past one level.

**Remember:** Bottom-up build-heap sifts down each internal node from index n/2 to 1, and each sift-down continues until the key is no larger than its children. Different construction methods give different valid heaps.

**Why each option:**
- (A) The result of sifting down from index 5 to index 1, with 45 sinking all the way to index 10.
- (B) A valid min-heap, but it is what inserting the keys one by one (sift-up) produces, not bottom-up build-heap.
- (C) Stops sifting 45 one level early; 45 at index 5 is larger than its child 18, so this is not a heap.
- (D) A sorted array is a min-heap, but build-heap does not sort; it only fixes parent-child order.