--- title: "Heap sort on 37, 33, 26, 92, ..." subject: "Data Structure and Algorithm" chapter: 7 key: "semester_4/data_structure_and_algorithm:heap-construct-12-element" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/heap-construct-12-element site: BCT Engineering --- # Heap sort on 37, 33, 26, 92, ... Data Structure and Algorithm · Chapter 7: Sorting - Asked in: 2073 Bhadra, 6 marks - Video: [Sort the following array using Heap sort? 66,33,40,20,50,88,60,11,77,30,45,65 | Hindi/Eng](https://www.youtube.com/watch?v=muOIfhJ_XWs) — EasyExamNotes.com - 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-construct-12-element - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7 ## Question Construct heap sort for the following given list with an algorithm: 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22. ## Short answer Build max-heap by heapifying from last parent: final heap array 92,86,48,33,57,22,26,25,12,37,42,18. Sorting phase repeatedly swaps max to end and re-heapifies. Final sorted list: 12,18,22,25,26,33,37,42,48,57,86,92. ## Answer Heap sort has two phases: (1) build a max-heap from the list, (2) repeatedly remove the largest element and put it at the end. #### Algorithm ```text HeapSort(a[0..n-1]) 1. for i = n/2 - 1 down to 0: Sift(a, i, n) /* build max-heap */ 2. for last = n-1 down to 1: swap a[0] and a[last] /* max goes to its place */ Sift(a, 0, last) /* heap size is now 'last' */ Sift(a, i, n): /* push a[i] down until parent >= children */ while 2i+1 < n: c = index of larger child of i if a[c] <= a[i] stop swap a[i], a[c]; i = c ``` #### Phase 1: build the heap List (index 0 to 11): 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22. The last parent is index 5 (n/2 − 1). | Step | Heapify node | Array | |---|---|---| | start | – | 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22 | | 1 | a[5] | 37, 33, 26, 92, 57, 22, 48, 25, 12, 86, 42, 18 | | 2 | a[4] | 37, 33, 26, 92, 86, 22, 48, 25, 12, 57, 42, 18 | | 3 | a[3] | 37, 33, 26, 92, 86, 22, 48, 25, 12, 57, 42, 18 | | 4 | a[2] | 37, 33, 48, 92, 86, 22, 26, 25, 12, 57, 42, 18 | | 5 | a[1] | 37, 92, 48, 33, 86, 22, 26, 25, 12, 57, 42, 18 | | 6 | a[0] | 92, 86, 48, 33, 57, 22, 26, 25, 12, 37, 42, 18 | Heap obtained: ```text level 0: 92 level 1: 86 48 level 2: 33 57 22 26 level 3: 25 12 37 42 18 ``` #### Phase 2: sorting Each pass swaps the root with the last heap element, shrinks the heap by one, and sifts the root down. | Pass | Max moved to end | Heap part after re-heapify | Sorted part | |---|---|---|---| | 1 | 92 (last position 12) | 86, 57, 48, 33, 42, 22, 26, 25, 12, 37, 18 | 92 | | 2 | 86 (last position 11) | 57, 42, 48, 33, 37, 22, 26, 25, 12, 18 | 86, 92 | | 3 | 57 (last position 10) | 48, 42, 26, 33, 37, 22, 18, 25, 12 | 57, 86, 92 | | 4 | 48 (last position 9) | 42, 37, 26, 33, 12, 22, 18, 25 | 48, 57, 86, 92 | | 5 | 42 (last position 8) | 37, 33, 26, 25, 12, 22, 18 | 42, 48, 57, 86, 92 | | 6 | 37 (last position 7) | 33, 25, 26, 18, 12, 22 | 37, 42, 48, 57, 86, 92 | | 7 | 33 (last position 6) | 26, 25, 22, 18, 12 | 33, 37, 42, 48, 57, 86, 92 | | 8 | 26 (last position 5) | 25, 18, 22, 12 | 26, 33, 37, 42, 48, 57, 86, 92 | | 9 | 25 (last position 4) | 22, 18, 12 | 25, 26, 33, 37, 42, 48, 57, 86, 92 | | 10 | 22 (last position 3) | 18, 12 | 22, 25, 26, 33, 37, 42, 48, 57, 86, 92 | | 11 | 18 (last position 2) | 12 | 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92 | | – | – | (empty) | 12, 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92 | **Sorted list: 12, 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92** Complexity: building O(n), n − 1 sift-downs of O(log n) each, so O(n log n) overall. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What are the two phases of heap sort? A. Partition then merge B. Build a max-heap, then repeatedly move the largest to the end and re-heapify C. Distribute then collect D. Divide then conquer Answer: B. Phase 1 builds the max-heap; phase 2 does n-1 root extractions. (Key point: Two phases) 2. For n = 12, from which index does heap building start and in which direction? A. Index 0 upward B. Index 11 downward C. Index 5 (n/2 - 1) down to 0 D. Index 6 up to 11 Answer: C. The last parent is n/2 - 1 = 5; leaves are already heaps. (Key point: Starting index) 3. What is at the root of the heap built from 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22? A. 37 B. 92 C. 86 D. 22 Answer: B. The max-heap root is the largest element, 92. (Key point: Heap root) 4. What is the overall complexity of heap sort? A. O(n) build plus n-1 sift-downs of O(log n), so O(n log n) B. O(n^2) C. O(log n) D. O(n) overall Answer: A. Building is O(n); the extractions dominate at O(n log n). (Key point: Complexity) ## Related in Data Structure and Algorithm - [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 - [Shell sort on 92, 83, 22, 49, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ashell-sort-trace) — Data Structure and Algorithm, chapter 7 - [Heap tree insertion and heap sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-insertion-and-sort) — Data Structure and Algorithm, chapter 7 - [Merge sort on 85, 76, 46, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-sort-trace-85-76) — 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 ## Related in other subjects - [Hardness of well water with strontium 25.26 mg/l](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Ahardness-bk81) — Water Supply Engineering, chapter 4