Min-Heap: Insert, Extract-Min, and Heapify Operations

Min-Heap Operations

A min-heap is a complete binary tree where every parent is smaller than or equal to its children. The minimum element is always at the root.

Array Representation

Heaps are stored as arrays using index math instead of pointers:

Parent of node i:      floor((i - 1) / 2)
Left child of node i:  2 * i + 1
Right child of node i: 2 * i + 2

Example: [1, 3, 5, 7, 9, 8, 6]

        1
       / \
      3    5
     / \  / \
    7   9 8   6

Insert — O(log n)

1. Add the new element at the end of the array (next available position in the tree).
2. Bubble up: Compare with parent. If smaller, swap. Repeat until the heap property is restored.

Insert 2 into [1, 3, 5, 7, 9, 8, 6]:
Step 1: [1, 3, 5, 7, 9, 8, 6, 2]  (added at end)
Step 2: Compare 2 with parent 7 -> swap: [1, 3, 5, 2, 9, 8, 6, 7]
Step 3: Compare 2 with parent 3 -> swap: [1, 2, 5, 3, 9, 8, 6, 7]
Step 4: Compare 2 with parent 1 -> no swap (2 > 1). Done.

Extract-Min — O(log n)

1. Remove the root (minimum element).
2. Move the last element to the root.
3. Bubble down: Compare with children. Swap with the smaller child if it is smaller. Repeat.

Extract from [1, 2, 5, 3, 9, 8, 6, 7]:
Step 1: Remove 1, move 7 to root: [7, 2, 5, 3, 9, 8, 6]
Step 2: Compare 7 with children 2, 5 -> swap with 2: [2, 7, 5, 3, 9, 8, 6]
Step 3: Compare 7 with children 3, 9 -> swap with 3: [2, 3, 5, 7, 9, 8, 6]
Step 4: 7 has no children smaller. Done.

Build Heap — O(n)

Building a heap from an unsorted array is O(n), not O(n log n):

1. Start from the last non-leaf node (index floor(n/2) - 1).
2. Apply bubble-down (heapify) to each node from bottom to top.

The O(n) complexity comes from the fact that most nodes are near the bottom of the tree and need only a few swaps.

Peek — O(1)

The minimum is always at index 0. No traversal needed.