Add the following numbers sequentially to an initially empty heap: $12, 5, 15, 9, 22, 41, 18, 16, 4, 13$

Q.) Add the following numbers sequentially to an initially empty heap: $12, 5, 15, 9, 22, 41, 18, 16, 4, 13$

 Subject: Data Structures

To add the given numbers to an initially empty heap, we need to decide whether we are constructing a min-heap or a max-heap. For this example, let's assume we are building a min-heap, where the smallest element is always at the root, and every parent node is smaller than its children.

Here's a step-by-step approach to adding the numbers to the heap:

  1. Start with an empty heap.

  2. Insert 12:

    • Add 12 as the root of the heap since the heap is empty.
   12
  1. Insert 5:
    • Add 5 as the left child of 12.
    • Since 5 is smaller than 12, swap them to maintain the min-heap property.
     5
    /
   12
  1. Insert 15:
    • Add 15 as the right child of 5. No swaps needed since 5 is still the smallest.
     5
    / \
   12  15
  1. Insert 9:
    • Add 9 as the left child of 12.
    • Swap 9 with 12 to maintain the min-heap property.
     5
    / \
   9   15
  /
 12
  1. Insert 22:
    • Add 22 as the right child of 9. No swaps needed.
     5
    / \
   9   15
  / \
 12  22
  1. Insert 41:
    • Add 41 as the left child of 15. No swaps needed.
     5
    / \
   9   15
  / \  /
 12 22 41
  1. Insert 18:
    • Add 18 as the right child of 15. No swaps needed.
     5
    / \
   9   15
  / \  / \
 12 22 41 18
  1. Insert 16:
    • Add 16 as the left child of 12.
    • Swap 16 with 12 since 16 is smaller. Then, compare 16 with 9, no swap needed as 9 is smaller.
     5
    / \
   9   15
  / \  / \
 16 22 41 18
 /
12

  1. Insert 4:

    • Add 4 as the right child of 16.
    • Swap 4 with 16, then with 9, and finally with 5 to maintain the min-heap property.
       4
  / \
 5   15
/ \  / \
9  22 41 18
/ \
12 16

  2. Insert 13:

    • Add 13 as the right child of 9.
    • No swaps needed as 9 is smaller than 13.
       4
  / \
 5   15
/ \  / \
9  22 41 18
/ \  /
12 16 13

The final min-heap structure after inserting all the numbers is:

   4
  / \
 5   15
/ \  / \
9 22 41 18
/ \  /
12 16 13

This is the min-heap after sequentially adding the given numbers. Each step ensures that the heap property is maintained by comparing the newly added element with its parent and swapping if necessary.