Min Heap
A min heap is a complete binary tree stored compactly in an array, with the smallest value always available at the root.
The Shape and the Property
A min heap combines two separate guarantees. The shape guarantee is that the tree is complete: every level is full except possibly the last, and the last level is filled from left to right. The ordering guarantee is the min-heap property: every parent value is less than or equal to each of its children.
Together, these guarantees make the minimum easy to find. Because every edge points from a smaller or equal parent to a larger or equal child, no descendant can be smaller than the root. The root is therefore the minimum element, so peek() is O(1).
Array Layout
Heaps are usually stored in an array rather than pointer nodes. For zero-based index i, the left child lives at 2i+1, the right child at 2i+2, and the parent at (i-1)/2 using integer division. A heap such as [1,3,5,4] represents root 1, children 3 and 5, and 4 as the left child of 3.
This layout works because the tree is complete. There are no interior gaps, so level-order positions map directly to contiguous array indices. That is why heaps have excellent memory locality and why operations can move through the tree with index arithmetic instead of object references.
Insert With Sift-Up
To insert into a min heap, append the new value at the end of the array. This preserves the complete-tree shape immediately, but it may violate the min-heap property with its parent. The repair is sift-up: while the new value is smaller than its parent, swap it with the parent and continue upward.
Only one root-to-leaf path can be affected. A complete binary tree with n nodes has height O(log n), so insertion is O(log n) time. The array may occasionally resize, but the heap-order work remains logarithmic.
Extract-Min With Sift-Down
To remove the minimum, take the root value, move the last array element into the root position, shrink the heap size, and repair downward. The shape remains complete because the removed physical slot was the last level-order position.
The repair is sift-down: compare the moved value with its smaller child, swap with that child if needed, and continue until both children are no smaller or the node becomes a leaf. Like insertion, extract-min touches one downward path, so it is O(log n) time.
Min-heap sift-up in an array
Appending preserves the complete-tree shape; siftUp restores the min-heap property by walking through parent indices (i-1)/2.
Key Takeaways
- A min heap is a complete binary tree where every parent is less than or equal to its children.
- The array layout maps index **i** to children **2i+1** and **2i+2**, with parent **(i-1)/2**.
- The root stores the minimum, so **peek()** is **O(1)**.
- Insert uses **sift-up** and extract-min uses **sift-down**, each costing **O(log n)**.