MinHeap

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