# Min Heap

## Problem Description

Implement a Min Heap data structure where the parent node is always smaller than or equal to its children, and the minimum element is always at the root.

## What is a Min Heap?

A min heap is a complete binary tree where each parent node has a value less than or equal to its children. The minimum element is always at the root.

## Characteristics

- **Time Complexity**:
  - Insert: O(log n)
  - Extract Min: O(log n)
  - Peek: O(1)
  - Build Heap: O(n)
- **Space Complexity**: O(n)
- **Heap Property**: parent ≤ children
- **Structure**: Complete binary tree

## Heap Property

For every node i:
- `heap[i] ≤ heap[2*i + 1]` (left child)
- `heap[i] ≤ heap[2*i + 2]` (right child)

## Core Operations

1. **insert(val)**: Add element maintaining heap property
2. **extractMin()**: Remove and return minimum (root)
3. **peek()**: View minimum without removing
4. **heapifyUp()**: Restore heap property upward
5. **heapifyDown()**: Restore heap property downward

## Your Task

Implement the following methods in `MinHeap.java`:

1. `insert(int val)` - Insert element
2. `extractMin()` - Remove and return minimum
3. `peek()` - Return minimum without removing
4. `heapifyUp(int index)` - Fix heap property upward
5. `heapifyDown(int index)` - Fix heap property downward

## Array Representation

For a node at index `i`:
- **Parent**: `(i - 1) / 2`
- **Left child**: `2 * i + 1`
- **Right child**: `2 * i + 2`

```
Array: [1, 3, 5, 7, 9, 11]
Tree:
       1
      / \
     3   5
    / \ /
   7  9 11
```

## How Insert Works

1. Add element at the end (to maintain complete tree)
2. Heapify up: compare with parent
3. If smaller than parent, swap
4. Repeat until heap property is satisfied

## How Extract Min Works

1. Save root value (minimum)
2. Move last element to root
3. Heapify down: compare with children
4. Swap with smaller child if necessary
5. Repeat until heap property is satisfied

## Test Cases to Consider

- Insert multiple elements
- Extract from heap with one element
- Extract all elements (should come out sorted)
- Peek without extracting
- Extract from empty heap (should throw exception)
- Insert and extract mixed operations

## Hints

- Use ArrayList for dynamic sizing
- Always add new elements at the end
- For heapifyUp: compare with parent and swap if needed
- For heapifyDown: compare with both children, swap with smaller
- Handle edge cases: empty heap, single element

## Applications

- Priority Queue implementation
- Dijkstra's shortest path algorithm
- Huffman coding
- Heap sort
- Finding k smallest elements
- Median maintenance
- Event-driven simulation

## Common Problems

1. Find k smallest elements in array
2. Merge k sorted lists
3. Find median in stream
4. Top K frequent elements
5. Task scheduler

## Follow-up Questions

1. How would you convert a max heap to min heap?
2. How would you find the kth smallest element using a heap?
3. How would you implement heap sort using this heap?
4. What's the difference between a heap and a binary search tree?

## Common Pitfalls

- Incorrect index calculations (parent/child formulas)
- Not handling empty heap errors
- Comparing with wrong child in heapifyDown
- Off-by-one errors
- Not maintaining complete tree property

## Min Heap vs Max Heap

| Property | Min Heap | Max Heap |
|----------|----------|----------|
| Root | Minimum | Maximum |
| Parent-Child | parent ≤ child | parent ≥ child |
| Use Case | Find minimum | Find maximum |

## Building a Heap

Two approaches:
1. **Insert one by one**: O(n log n)
2. **Heapify bottom-up**: O(n) - more efficient!

## Edge Cases

- Empty heap operations
- Single element heap
- Heap with duplicate values
- Large dataset performance

## Related Data Structures

- Max Heap
- Priority Queue
- Binary Search Tree
- Binomial Heap
- Fibonacci Heap