- 2072 Magh · 8 marks
Heap tree insertion and heap sort
Short answer
Insert each value at the end and bubble up: final max-heap array is 29,28,25,23,18,14,11,12,21. Sort by repeatedly moving root to end and sifting down: final ascending order 11,12,14,18,21,23,25,28,29. Overall time O(n log n).
Create a heap tree showing each insertion steps for the following data. Use the same heap tree to sort the data showing each intermediate steps: 14, 12, 25, 18, 21, 29, 11, 28, 23.
A max-heap is built by inserting keys one at a time at the next free position (end of the array) and moving the key up (swapping with its parent) while it is larger than its parent.
Part 1: insertion of 14, 12, 25, 18, 21, 29, 11, 28, 23
| Step | Insert | Array (heap) after step | Moves |
|---|---|---|---|
| 1 | 14 | 14 | none |
| 2 | 12 | 14, 12 | none |
| 3 | 25 | 25, 12, 14 | 25↔14 |
| 4 | 18 | 25, 18, 14, 12 | 18↔12 |
| 5 | 21 | 25, 21, 14, 12, 18 | 21↔18 |
| 6 | 29 | 29, 21, 25, 12, 18, 14 | 29↔14, 29↔25 |
| 7 | 11 | 29, 21, 25, 12, 18, 14, 11 | none |
| 8 | 28 | 29, 28, 25, 21, 18, 14, 11, 12 | 28↔12, 28↔21 |
| 9 | 23 | 29, 28, 25, 23, 18, 14, 11, 12, 21 | 23↔21 |
Final heap (array positions 1–9):
level 0: 29
level 1: 28 25
level 2: 23 18 14 11
level 3: 12 21
Tree: 29
/ \
28 25
/ \ / \
23 18 14 11
/ \
12 21
Part 2: heap sort using the same heap
Swap the root with the last element of the heap, reduce the heap size, and sift the new root down.
| Pass | Max moved to end | Heap part after re-heapify | Sorted part |
|---|---|---|---|
| 1 | 29 (last position 9) | 28, 23, 25, 21, 18, 14, 11, 12 | 29 |
| 2 | 28 (last position 8) | 25, 23, 14, 21, 18, 12, 11 | 28, 29 |
| 3 | 25 (last position 7) | 23, 21, 14, 11, 18, 12 | 25, 28, 29 |
| 4 | 23 (last position 6) | 21, 18, 14, 11, 12 | 23, 25, 28, 29 |
| 5 | 21 (last position 5) | 18, 12, 14, 11 | 21, 23, 25, 28, 29 |
| 6 | 18 (last position 4) | 14, 12, 11 | 18, 21, 23, 25, 28, 29 |
| 7 | 14 (last position 3) | 12, 11 | 14, 18, 21, 23, 25, 28, 29 |
| 8 | 12 (last position 2) | 11 | 12, 14, 18, 21, 23, 25, 28, 29 |
| – | – | (empty) | 11, 12, 14, 18, 21, 23, 25, 28, 29 |
Sorted data (ascending): 11, 12, 14, 18, 21, 23, 25, 28, 29
Insertion takes O(log n) per key; the sorting phase takes n − 1 sift-downs of O(log n), so the total is O(n log n).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- B-tree from 78, 21, 14, 11, 97, 85, 74, 63 · Data Structure and Algorithm, chapter 6 · asked 2×
- Heap sort on 37, 33, 26, 92, ... · Data Structure and Algorithm, chapter 7
- Merge sort on 47, 27, 56, 23, ... · Data Structure and Algorithm, chapter 7
- Heap sort with example · Data Structure and Algorithm, chapter 7
- B-tree insertion algorithm; AVL of months · Data Structure and Algorithm, chapter 6 · asked 2×
- Radix sort on 25, 57, 48, 37, ... · Data Structure and Algorithm, chapter 7
- Subnet 202.70.91.0/24 for 25, 16, 29, 11 · Computer Networks and Security, chapter 4 · asked 2×
- K-map Σ(1,2,3,8,9,10,11,14)+d(0,4,12), NAND · Digital Logic, chapter 3 · asked 5×
- Intermediate beam for 18 m x 6 m office hall · Design of Steel and Timber Structure, chapter 7
- Booth multiplication of 23 × -21 (6 bits) · Computer Organization and Architecture, chapter 5