PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q8(b)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Sorting Algorithms

Question

Consider the following max heap: 50, 30, 20, 15, 10, 8, 16. Insert a new node with value 60.

Solution

Initial Max-Heap Structure Analysis: The initial heap elements in array form:

Array indices: to . In an array representation of a complete binary tree (0-indexed):

Initial tree diagram:

            50 [idx 0]
          /            \
     30 [idx 1]        20 [idx 2]
     /        \        /        \
 15 [idx 3] 10 [idx 4] 8 [idx 5] 16 [idx 6]

Verification of max-heap property: , , .

Insertion at the Next Available Complete Tree Position: To maintain the shape property of a complete binary tree, the new key 60 is placed at the end of the array at index (as the left child of node at index , which is 15):

Tree at this stage:

            50
          /    \
        30      20
       /  \    /  \
     15   10  8   16
    /
  60 [idx 7]

The max-heap property is violated because child 60 > parent 15. We must heapify-up (percolate-up / swim).

Percolate-Up (Swim) Iteration 1:

Tree at this stage:

            50
          /    \
        30      20
       /  \    /  \
     60   10  8   16
    /
  15

Percolate-Up (Swim) Iteration 2:

Tree at this stage:

            50
          /    \
        60      20
       /  \    /  \
     30   10  8   16
    /
  15

Percolate-Up (Swim) Iteration 3:

Final Max-Heap Tree and Array: Final array representation:

Final complete binary tree:

                 60 [idx 0]
               /            \
          50 [idx 1]        20 [idx 2]
          /        \        /        \
      30 [idx 3] 10 [idx 4] 8 [idx 5] 16 [idx 6]
      /
   15 [idx 7]

Property Check:

All parent-child relationships strictly satisfy the max-heap condition in time.

Answer:

After inserting 60 into the max-heap:

Node 60 becomes the new root of the max-heap.

All past exam questions for Data Structure and Algorithms