Introduction

The 2n/3 term in max-heapify analysis does not mean heapify touches two-thirds of all nodes directly. It comes from bounding the size of the largest child subtree in a nearly complete binary heap, which is what matters in the recurrence for the worst-case running time.

Where the Recurrence Comes From

MAX-HEAPIFY compares a node with its children, possibly swaps with the larger child, and then continues recursively down one subtree.

That gives a recurrence of the form:

T(n) <= T(size of larger child subtree) + O(1)

So the key question becomes:

How large can the larger child subtree be in a heap with n nodes?

A Heap Is a Complete Binary Tree

A max-heap is a complete binary tree, which means all levels are full except possibly the last, and the last level is filled from left to right.

Because of that structure, the two child subtrees of the root cannot be arbitrarily unbalanced. One child can be larger than the other, but not by an unlimited amount.

This is where the 2n/3 bound appears.

Intuition for the 2n/3 Bound

Suppose the root has:

• one left subtree
• one right subtree

In the worst case, the last level is only partially filled, and the larger child subtree gets as many of those extra nodes as possible. Even then, the larger subtree cannot exceed about two-thirds of the total nodes.

That is why CLRS-style analysis often writes:

T(n) <= T(2n/3) + O(1)

It is an upper bound on the recursive problem size, not a count of nodes actually modified.

A More Concrete Derivation

Assume the heap has height h, where the root is at height 0.

The largest a child subtree can get is when:

• one child has a full tree of height h - 1
• the other child has the smallest valid complete-tree shape for that overall heap size

In a complete binary tree, the larger child subtree can have at most:

2^(h) - 1

while the total tree has at least:

1 + (2^(h) - 1) + (2^(h-1) - 1)

nodes in the most unbalanced valid case.

That total simplifies to:

3 * 2^(h-1) - 1

So the larger subtree is at most roughly:

(2^h - 1) / (3 * 2^(h-1) - 1)

of the total, which is bounded by about 2/3.

That is the source of the textbook recurrence.

Why This Still Leads to O(log n)

Once you have:

T(n) <= T(2n/3) + O(1)

you can solve it by repeated substitution.

After k recursive levels:

T(n) <= T((2/3)^k n) + O(k)

The recursion stops when the remaining subtree size becomes constant. That happens when:

(2/3)^k n = O(1)

which implies:

k = O(log n)

So the worst-case time for MAX-HEAPIFY is still logarithmic.

Example Walkdown

Here is a simple Python version of heapify:

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        if right < heap_size and arr[right] > arr[largest]:
10            largest = right
11
12        if largest == i:
13            return
14
15        arr[i], arr[largest] = arr[largest], arr[i]
16        i = largest
17
18
19data = [1, 14, 10, 8, 7, 9, 3, 2, 4, 6]
20max_heapify(data, 0, len(data))
21print(data)

Notice that the algorithm follows only one downward path. That is another reason the work is logarithmic rather than linear in the number of nodes.

Common Pitfalls

The biggest mistake is thinking 2n/3 means heapify actually updates two-thirds of all nodes. It does not. It is only a bound on the size of the recursive subtree.

Another issue is forgetting that heaps are complete binary trees. The 2n/3 bound depends on that shape restriction.

A third problem is treating the recurrence as if heapify branches into both subtrees. In reality it continues into only one child after the swap.

Summary

• The 2n/3 term bounds the size of the largest child subtree in a complete binary heap.
• It appears in the recurrence T(n) <= T(2n/3) + O(1).
• 'MAX-HEAPIFY recurses down only one subtree, not both.'
• Repeated substitution of that recurrence gives O(log n).
• The bound is about subtree size, not about the number of nodes directly modified.