--- title: "Heap tree insertion and heap sort" subject: "Data Structure and Algorithm" chapter: 7 key: "semester_4/data_structure_and_algorithm:heap-insertion-and-sort" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/heap-insertion-and-sort site: BCT Engineering --- # Heap tree insertion and heap sort Data Structure and Algorithm · Chapter 7: Sorting - Asked in: 2072 Magh, 8 marks - Video: [Heaps and Heapsort - Simply Explained](https://www.youtube.com/watch?v=pY-cH7rti4U) — Maaneth De Silva - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/heap-insertion-and-sort - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7 ## Question 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. ## 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). ## Answer 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): ```text level 0: 29 level 1: 28 25 level 2: 23 18 14 11 level 3: 12 21 ``` ```text 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a key inserted into a max-heap? A. At the root, then sifted down B. At the next free position at the end, then swapped upward while larger than its parent C. At a random leaf with no moves D. In sorted position in the array Answer: B. Insertion places the key at the end and moves it up. (Key point: Insertion method) 2. After inserting 14, 12, 25, 18, 21, 29, 11, 28, 23, what is at the root? A. 14 B. 23 C. 29 D. 28 Answer: C. 29 is the largest key, so it moves up to the root. (Key point: Final root) 3. How is the same heap used to sort? A. Swap the root with the last heap element, reduce size, sift the new root down B. Delete leaves from left to right C. Read the array from left to right D. Insert keys again in reverse order Answer: A. Each pass puts the maximum at the end of the array. (Key point: Sorting phase) 4. What is the total time of this heap sort? A. O(n^2) B. O(n log n) C. O(n) D. O(log n) Answer: B. Insertion is O(log n) per key and the sort phase does n-1 sift-downs of O(log n). (Key point: Complexity) ## Related in Data Structure and Algorithm - [B-tree from 78, 21, 14, 11, 97, 85, 74, 63](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-build-78-21-14) — Data Structure and Algorithm, chapter 6, asked 2× - [Heap sort on 37, 33, 26, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-construct-12-element) — Data Structure and Algorithm, chapter 7 - [Merge sort on 47, 27, 56, 23, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-47-27) — Data Structure and Algorithm, chapter 7 - [Heap sort with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-sort-example) — Data Structure and Algorithm, chapter 7 - [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2× - [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7 ## Related in other subjects - [Subnet 202.70.91.0/24 for 25, 16, 29, 11](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Asubnetting-202-70-91) — Computer Networks and Security, chapter 4, asked 2× - [K-map Σ(1,2,3,8,9,10,11,14)+d(0,4,12), NAND](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Akmap-nand-1238-dc-0412) — Digital Logic, chapter 3, asked 5× - [Intermediate beam for 18 m x 6 m office hall](https://www.bctengineer.com/question.md?key=semester_6%2Fdesign_of_steel_and_timber_structure%3Aoffice-hall-18x6-intermediate-beam) — Design of Steel and Timber Structure, chapter 7 - [Booth multiplication of 23 × -21 (6 bits)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Abooth-23x-21) — Computer Organization and Architecture, chapter 5