Past exam question: 2063 Baishakh (Regular / Back), Q9
Open in the Padhaiko appQuestion
Define heap structure. Construct heap for these elements 2,8,6,1,10,15,3,12,11. Show the steps clearly.
Solution
Definition of Heap Structure: A binary heap is an almost complete binary tree that satisfies the heap-order property:
- Max-Heap: Every parent's key is both of its children's keys (maximum at root).
- Min-Heap: Every parent's key is both of its children's keys (minimum at root).
Top-Down Max-Heap Construction for 2, 8, 6, 1, 10, 15, 3, 12, 11: Insert each element at the end of the array and percolate up (swap with parent while greater):
- Insert
2:[2] - Insert
8:[2, 8][8, 2] - Insert
6:[8, 2, 6] - Insert
1:[8, 2, 6, 1] - Insert
10:[8, 2, 6, 1, 10][10, 8, 6, 1, 2] - Insert
15:[10, 8, 6, 1, 2, 15][15, 8, 10, 1, 2, 6] - Insert
3:[15, 8, 10, 1, 2, 6, 3] - Insert
12:[15, 8, 10, 1, 2, 6, 3, 12][15, 12, 10, 8, 2, 6, 3, 1] - Insert
11:[15, 12, 10, 8, 2, 6, 3, 1, 11][15, 12, 10, 11, 2, 6, 3, 1, 8]
Answer:
Constructed Max-Heap array: [15, 12, 10, 11, 2, 6, 3, 1, 8] (root 15, children 12, 10, etc.).