Past exam question: 2077 Chaitra (Regular), Q8
Open in the Padhaiko appQuestion
Create a heap tree showing each insertion steps for the following data: 28, 24, 50, 36, 42, 58, 22, 56, 46. Use same heap tree to sort the data showing each intermediate step.
Solution
Top-Down Max-Heap Construction (Sequential Insertion): Inserting one by one and sifting up (percolate-up) whenever child parent:
- Insert
28:[28] - Insert
24:[28, 24] - Insert
50:[28, 24, 50][50, 24, 28] - Insert
36:[50, 24, 28, 36][50, 36, 28, 24] - Insert
42:[50, 36, 28, 24, 42][50, 42, 28, 24, 36] - Insert
58:[50, 42, 28, 24, 36, 58][50, 42, 58, 24, 36, 28][58, 42, 50, 24, 36, 28] - Insert
22:[58, 42, 50, 24, 36, 28, 22] - Insert
56:[58, 42, 50, 24, 36, 28, 22, 56][58, 56, 50, 42, 36, 28, 22, 24] - Insert
46:[58, 56, 50, 42, 36, 28, 22, 24, 46][58, 56, 50, 46, 36, 28, 22, 24, 42]
Heap Sort Extraction Passes (Swap Root with Last Unsorted Element & Heapify Down):
- Extract
58(swap with42), heapify size 8[56, 46, 50, 42, 36, 28, 22, 24 | 58] - Extract
56(swap with24), heapify size 7[50, 46, 28, 42, 36, 24, 22 | 56, 58] - Extract
50(swap with22), heapify size 6[46, 42, 28, 22, 36, 24 | 50, 56, 58] - Extract
46(swap with24), heapify size 5[42, 36, 28, 22, 24 | 46, 50, 56, 58] - Extract
42(swap with24), heapify size 4[36, 24, 28, 22 | 42, 46, 50, 56, 58] - Extract
36(swap with22), heapify size 3[28, 24, 22 | 36, 42, 46, 50, 56, 58] - Extract
28(swap with22), heapify size 2[24, 22 | 28, 36, 42, 46, 50, 56, 58] - Extract
24(swap with22), size 1[22, 24, 28, 36, 42, 46, 50, 56, 58]
Answer:
- Constructed Max-Heap:
[58, 56, 50, 46, 36, 28, 22, 24, 42]. - Sorted Sequence:
22, 24, 28, 36, 42, 46, 50, 56, 58.