PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q7

Data Structure and Algorithms · 11 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Create the heap structure from the following sequence data: 12, 10, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an empty heap. And sort them using heap sort.

Solution

Top-Down Max-Heap Insertion (15 Elements): Inserting each key at the next complete-tree position and sifting up (percolate-up):

Heap Sort Extraction Passes (Root Swapped to End & Heapify Down):

  1. Extract 15 [14, 12, 13, 10, 9, 8, 11, 2, 3, 6, 7, 1, 4, 5 | 15]
  2. Extract 14 [13, 12, 11, 10, 9, 8, 5, 2, 3, 6, 7, 1, 4 | 14, 15]
  3. Extract 13 [12, 10, 11, 4, 9, 8, 5, 2, 3, 6, 7, 1 | 13, 14, 15]
  4. Extract 12 [11, 10, 8, 4, 9, 1, 5, 2, 3, 6, 7 | 12..15]
  5. Extract 11 [10, 9, 8, 4, 7, 1, 5, 2, 3, 6 | 11..15]
  6. Extract 10 [9, 7, 8, 4, 6, 1, 5, 2, 3 | 10..15]
  7. Extract 9 [8, 7, 5, 4, 6, 1, 3, 2 | 9..15]
  8. Extract 8 [7, 6, 5, 4, 2, 1, 3 | 8..15]
  9. Extract 7 [6, 4, 5, 3, 2, 1 | 7..15]
  10. Extract 6 [5, 4, 1, 3, 2 | 6..15]
  11. Extract 5 [4, 3, 1, 2 | 5..15]
  12. Extract 4 [3, 2, 1 | 4..15]
  13. Extract 3 [2, 1 | 3..15]
  14. Extract 2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Answer:

All past exam questions for Data Structure and Algorithms