Past exam question: 2066 Bhadra (Regular / Back), Q7
Open in the Padhaiko appQuestion
Create the heap structure from the following sequence data: 12, 10, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an empty heap. And sort them using heap sort.
Solution
Top-Down Max-Heap Insertion (15 Elements): Inserting each key at the next complete-tree position and sifting up (percolate-up):
12, 10, 1:[12, 10, 1]+14:14swaps with10, then12[14, 12, 1, 10]+6, +5, +8:8swaps with1[14, 12, 8, 10, 6, 5, 1]+15:15swaps10 -> 12 -> 14to root[15, 14, 8, 12, 6, 5, 1, 10]+3, +9, +7:9swaps6;7swaps6[15, 14, 8, 12, 9, 5, 1, 10, 3, 6, 7]+4, +11, +13, +2:11swaps5 -> 8;13swaps1 -> 11Final Max-Heap:[15, 14, 13, 12, 9, 8, 11, 10, 3, 6, 7, 1, 4, 5, 2]
Heap Sort Extraction Passes (Root Swapped to End & Heapify Down):
- Extract
15[14, 12, 13, 10, 9, 8, 11, 2, 3, 6, 7, 1, 4, 5 | 15] - Extract
14[13, 12, 11, 10, 9, 8, 5, 2, 3, 6, 7, 1, 4 | 14, 15] - Extract
13[12, 10, 11, 4, 9, 8, 5, 2, 3, 6, 7, 1 | 13, 14, 15] - Extract
12[11, 10, 8, 4, 9, 1, 5, 2, 3, 6, 7 | 12..15] - Extract
11[10, 9, 8, 4, 7, 1, 5, 2, 3, 6 | 11..15] - Extract
10[9, 7, 8, 4, 6, 1, 5, 2, 3 | 10..15] - Extract
9[8, 7, 5, 4, 6, 1, 3, 2 | 9..15] - Extract
8[7, 6, 5, 4, 2, 1, 3 | 8..15] - Extract
7[6, 4, 5, 3, 2, 1 | 7..15] - Extract
6[5, 4, 1, 3, 2 | 6..15] - Extract
5[4, 3, 1, 2 | 5..15] - Extract
4[3, 2, 1 | 4..15] - Extract
3[2, 1 | 3..15] - Extract
2[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Answer:
- Constructed Max-Heap:
[15, 14, 13, 12, 9, 8, 11, 10, 3, 6, 7, 1, 4, 5, 2]. - Sorted Output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.