Min-Heap

data-structures algorithms

Definition

Min-Heap

A min-heap is a heap that satisfies the min-heap property: for every node $i$ other than the root, the value of the parent is at most the value of the node itself:

$$A[\mathrm{parent}(i)]\le A[i]$$

Consequently, the smallest element in a min-heap is always stored at the root, and the values in any path from the root to a leaf are in non-decreasing order.

Operations

Min-Heapify

The $min-heapify$ procedure maintains the min-heap property. If a node $i$ violates the property by being larger than its children, it is swapped with its smallest child, and the process continues recursively down the tree.

Extract Min

To extract the minimum element:

1. Copy the root value (the minimum).
2. Replace the root with the last element in the array.
3. Decrease the heap size.
4. Call $min-heapify$ on the root to restore the heap property.

Insert

To insert a new element $x$:

1. Add $x$ at the end of the heap.
2. “Bubble up” (or $decrease-key$): compare $x$ with its parent and swap if $x$ is smaller, repeating until the min-heap property is satisfied.

Complexity

The time complexity for min-heap operations is identical to max-heaps:

• Min-Heapify: $O(\log n)$
• Insert: $O(\log n)$
• Extract-Min: $O(\log n)$
• Build-Min-Heap: $O(n)$