Introduction

max-heapify is the operation that repairs one broken node in a max-heap by pushing it downward until the heap property is restored. Although heaps are drawn as binary trees, most real implementations store them in arrays because the parent-child relationships are easy to compute from indices.

What max-heapify assumes

max-heapify does not turn an arbitrary tree into a heap in a single call. It assumes the left and right subtrees already satisfy the max-heap rule and only the current node may be too small.

For a zero-based array heap:

• left child is at 2 * i + 1
• right child is at 2 * i + 2
• parent is at (i - 1) // 2

The heap rule is simple: every parent value must be greater than or equal to its children.

Iterative implementation

An iterative version is efficient and avoids recursion depth concerns.

1def max_heapify(arr, i, heap_size):
2    while True:
3        left = 2 * i + 1
4        right = 2 * i + 2
5        largest = i
6
7        if left < heap_size and arr[left] > arr[largest]:
8            largest = left
9
10        if right < heap_size and arr[right] > arr[largest]:
11            largest = right
12
13        if largest == i:
14            return
15
16        arr[i], arr[largest] = arr[largest], arr[i]
17        i = largest
18
19
20values = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
21max_heapify(values, 1, len(values))
22print(values)

This compares the node at index i with its children, swaps with the larger child if needed, and repeats until the node reaches a valid position.

Recursive version

Textbooks often show the recursive form because it mirrors the tree definition directly.

1def max_heapify_recursive(arr, i, heap_size):
2    left = 2 * i + 1
3    right = 2 * i + 2
4    largest = i
5
6    if left < heap_size and arr[left] > arr[largest]:
7        largest = left
8
9    if right < heap_size and arr[right] > arr[largest]:
10        largest = right
11
12    if largest != i:
13        arr[i], arr[largest] = arr[largest], arr[i]
14        max_heapify_recursive(arr, largest, heap_size)

Both versions run in O(log n) because the element can move down only one level at a time and a heap has logarithmic height.

Build a full max-heap from an array

To heapify an entire array, call max_heapify from the last non-leaf node back to the root.

1def build_max_heap(arr):
2    heap_size = len(arr)
3    for i in range((heap_size // 2) - 1, -1, -1):
4        max_heapify(arr, i, heap_size)
5
6
7data = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
8build_max_heap(data)
9print(data)

This bottom-up construction runs in O(n), which is better than repeatedly inserting elements one by one.

Why heaps are usually arrays, not pointer trees

People often say "heapify a binary tree," but heaps are meant to be complete binary trees. Arrays represent complete trees naturally without storing explicit pointers.

If you literally have a node-based binary tree, you can still apply the same comparison-and-swap idea, but keeping the structure complete becomes awkward. In practice, when the goal is a heap, array storage is the standard representation.

Where max-heapify is used

You use this operation whenever the root of a valid heap becomes suspect. Common examples include:

• heap sort after swapping the root with the last element
• priority queues after removing the maximum
• rebuilding a heap after replacing the root value

For example, removing the maximum from a heap usually means:

1. move the last element to the root
2. shrink the heap size
3. call max_heapify on index 0

That sequence restores the heap property efficiently.

Common Pitfalls

The biggest mistake is assuming one call to max_heapify can convert any random array into a max-heap. It cannot. The function assumes the child subtrees are already heaps.

Another issue is mixing zero-based and one-based formulas. Many textbook formulas use left = 2i and right = 2i + 1, which apply to one-based indexing, not Python or C++ arrays indexed from zero.

Developers also confuse heaps with binary search trees. A heap guarantees that each parent dominates its children, but it does not keep the entire structure sorted left to right.

Finally, be careful with heap_size. During heap sort, the array length stays the same while the active heap shrinks. Passing the full array length after each extraction breaks the algorithm.

Summary

• 'max-heapify fixes one out-of-place node by moving it downward.'
• It assumes both child subtrees already satisfy the max-heap property.
• In zero-based arrays, children of index i are at 2 * i + 1 and 2 * i + 2.
• A single call is O(log n), while full bottom-up heap construction is O(n).
• Heaps are usually stored as arrays because complete binary trees map to arrays naturally.