PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Define heap structure. Construct heap for these elements 2,8,6,1,10,15,3,12,11. Show the steps clearly.

Solution

Definition of Heap Structure: A binary heap is an almost complete binary tree that satisfies the heap-order property:

Top-Down Max-Heap Construction for 2, 8, 6, 1, 10, 15, 3, 12, 11: Insert each element at the end of the array and percolate up (swap with parent while greater):

  1. Insert 2: [2]
  2. Insert 8: [2, 8] [8, 2]
  3. Insert 6: [8, 2, 6]
  4. Insert 1: [8, 2, 6, 1]
  5. Insert 10: [8, 2, 6, 1, 10] [10, 8, 6, 1, 2]
  6. Insert 15: [10, 8, 6, 1, 2, 15] [15, 8, 10, 1, 2, 6]
  7. Insert 3: [15, 8, 10, 1, 2, 6, 3]
  8. Insert 12: [15, 8, 10, 1, 2, 6, 3, 12] [15, 12, 10, 8, 2, 6, 3, 1]
  9. Insert 11: [15, 12, 10, 8, 2, 6, 3, 1, 11] [15, 12, 10, 11, 2, 6, 3, 1, 8]
Answer:

Constructed Max-Heap array: [15, 12, 10, 11, 2, 6, 3, 1, 8] (root 15, children 12, 10, etc.).

All past exam questions for Data Structure and Algorithms