Heapify Operation

Heapify maintains the heap property by moving elements up or down the heap.

Heapify Down

When an element violates the heap property, we “heapify down” by comparing with children and swapping if needed.

Implementation

Building a Heap

To build a max heap from an array, heapify all non-leaf nodes from bottom to top.

Key Points

1. Start from bottom: Heapify non-leaf nodes from bottom up
2. Compare with children: Check both left and right children
3. Swap if needed: Move larger child up
4. Recurse: Continue heapifying the affected subtree

What’s Next?

Now that you understand heapify, let’s see the complete heap sort algorithm.