Heapify
Heapify is the local sift-down repair that restores the heap property at one index when its child subtrees are already valid heaps.
The Local Repair Problem
In most interview discussions, heapify means sift-down from one node. The situation is local: the left and right child subtrees are already heaps, but the value at the current index may be too large for a min heap or too small for a max heap.
Because the child subtrees are valid, the only possible violation lies on a downward path. Fix the current node against the better child, then repeat in the child position where the moved value landed.
Choosing the Child
For a min heap, compare the current value with the smaller child. If the current value is less than or equal to both children, the min-heap property holds and the repair stops. Otherwise, swap with the smaller child, because that child is the only one that can safely become the parent of both child positions.
For a max heap, reverse the comparison and swap with the larger child. The shape never changes during heapify; only values move within the same array positions such as [7,3,5,4] becoming [3,4,5,7] after repeated downward swaps.
Why It Is O(log n)
Each swap moves the candidate value down exactly one level. A complete binary tree with n elements has height O(log n), so a single sift-down can perform at most O(log n) swaps and comparisons.
This bound is used by poll() after the last element is moved to the root. It is also the primitive used by build-heap, where the same local repair is applied to many internal nodes in a carefully chosen order.
Invariant to State in Interviews
A strong explanation says what is already true before heapify starts: both child subtrees satisfy the heap property. After each swap, the parent position is fixed, and any remaining violation moves down into exactly one child subtree. When the loop stops, no violation remains.
That invariant prevents a common mistake: trying to sort the whole array during heapify. Heapify does not make the array sorted. It restores local heap order, which is enough for priority queue operations.
Sift-down heapify for a min heap
The helper assumes the child subtrees are already heaps. It repeatedly swaps with the smaller child until the current index satisfies the min-heap property.
Key Takeaways
- Heapify usually means a local **sift-down** repair from one array index.
- For a min heap, swap with the smaller child; for a max heap, swap with the larger child.
- A single heapify is **O(log n)** because it moves down at most one tree height.
- Heapify restores heap order, not sorted array order.