Building a Minimum Heap (Min-Heap)

Introduction

• Minimum Heap (Min-Heap): A binary tree where the root node is the smallest element.
• Goal: Build a min-heap from an array of input elements.
• Method Used: Williams method (inserting elements one by one into an empty heap).

Steps to Build a Min-Heap

1. Start with an empty heap
2. Insert elements one by one, ensuring the heap property is maintained at each step.
   • Heap Property: Each parent node is less than or equal to its child nodes.

Example Walkthrough

Initial Array

[3, 1, 6, 5, 2, 4]

Step 1: Insert 3

• Add 3

Step 2: Insert 1

• Insert 1 to left of 3
• Swap 1 and 3 to maintain heap property
• Heap after swap:

  1
  /
  

3

### Step 3: Insert 6
- Insert 6 to right of 1
- **Heap is correct**: 

1 /
3 6

### Step 4: Insert 5
- Insert 5 to left of 3
- **Heap is correct** 

1 /
3 6 / 5

### Step 5: Insert 2
- Insert 2 to right of 3
- Swap 2 with 3
- Swap 2 with 1
- **Heap after swaps**: 

1 /
2 6 /
5 3

### Step 6: Insert 4
- Insert 4 to left of 6
- Swap 4 with 6
- **Heap is correct**: 

1 /
2 4 / \ / 5 3 6

## Final Heap as Array

[1, 2, 4, 5, 3, 6]

## Conclusion
- Maintaining the heap property requires checking and potentially swapping positions during each insertion.
- Following this process ensures a functional min-heap.