PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Create a heap tree showing each insertion steps for the following data: 28, 24, 50, 36, 42, 58, 22, 56, 46. Use same heap tree to sort the data showing each intermediate step.

Solution

Top-Down Max-Heap Construction (Sequential Insertion): Inserting one by one and sifting up (percolate-up) whenever child parent:

  1. Insert 28: [28]
  2. Insert 24: [28, 24]
  3. Insert 50: [28, 24, 50] [50, 24, 28]
  4. Insert 36: [50, 24, 28, 36] [50, 36, 28, 24]
  5. Insert 42: [50, 36, 28, 24, 42] [50, 42, 28, 24, 36]
  6. Insert 58: [50, 42, 28, 24, 36, 58] [50, 42, 58, 24, 36, 28] [58, 42, 50, 24, 36, 28]
  7. Insert 22: [58, 42, 50, 24, 36, 28, 22]
  8. Insert 56: [58, 42, 50, 24, 36, 28, 22, 56] [58, 56, 50, 42, 36, 28, 22, 24]
  9. Insert 46: [58, 56, 50, 42, 36, 28, 22, 24, 46] [58, 56, 50, 46, 36, 28, 22, 24, 42]

Heap Sort Extraction Passes (Swap Root with Last Unsorted Element & Heapify Down):

  1. Extract 58 (swap with 42), heapify size 8 [56, 46, 50, 42, 36, 28, 22, 24 | 58]
  2. Extract 56 (swap with 24), heapify size 7 [50, 46, 28, 42, 36, 24, 22 | 56, 58]
  3. Extract 50 (swap with 22), heapify size 6 [46, 42, 28, 22, 36, 24 | 50, 56, 58]
  4. Extract 46 (swap with 24), heapify size 5 [42, 36, 28, 22, 24 | 46, 50, 56, 58]
  5. Extract 42 (swap with 24), heapify size 4 [36, 24, 28, 22 | 42, 46, 50, 56, 58]
  6. Extract 36 (swap with 22), heapify size 3 [28, 24, 22 | 36, 42, 46, 50, 56, 58]
  7. Extract 28 (swap with 22), heapify size 2 [24, 22 | 28, 36, 42, 46, 50, 56, 58]
  8. Extract 24 (swap with 22), size 1 [22, 24, 28, 36, 42, 46, 50, 56, 58]
Answer:

All past exam questions for Data Structure and Algorithms