Introduction

At first glance, heap construction looks like it should cost O(n log n) because inserting one element into a heap costs O(log n), and doing that n times suggests n log n. But that reasoning applies to repeated insertion, not to Floyd's bottom-up heap construction algorithm. The bottom-up method is O(n) because most nodes are near the leaves, and nodes near the leaves are cheap to heapify.

The Expensive Intuition Is Incomplete

If you build a heap this way:

1. start with an empty heap
2. insert each element one by one

then yes, the total cost is typically O(n log n).

But there is another method: treat the whole array as a nearly complete binary tree and call heapify from the last internal node upward.

1def build_heap(arr):
2    n = len(arr)
3    for i in range(n // 2 - 1, -1, -1):
4        sift_down(arr, i, n)

That is the linear-time algorithm people mean when they say heap construction is O(n).

Why Bottom-Up Heapify Is Cheaper

Heapify on one node can cost up to the height of that node, not the height of the entire tree. Nodes at the bottom have height 0, nodes just above them have height 1, and only a tiny number of nodes are near the root with large height.

So the total work is not:

n times log n

It is closer to:

sum over all nodes of node height

That sum turns out to be linear in n for a complete binary tree.

The Key Counting Argument

In a complete binary tree:

• about n/2 nodes are leaves, so their heapify cost is 0
• about n/4 nodes have height 1
• about n/8 nodes have height 2
• and so on

So the total work is bounded by:

(n/4)*1 + (n/8)*2 + (n/16)*3 + ...

Factor out n:

n * (1/4 + 2/8 + 3/16 + ...)

The infinite series in parentheses converges to a constant, so the whole expression is O(n).

That is the real reason. The average node is cheap to fix because most nodes live low in the tree.

A Concrete Example

Suppose you have this array:

arr = [9, 4, 7, 1, -2, 6, 5]

You can build a min-heap bottom-up like this:

1def sift_down(arr, i, n):
2    while True:
3        left = 2 * i + 1
4        right = 2 * i + 2
5        smallest = i
6
7        if left < n and arr[left] < arr[smallest]:
8            smallest = left
9        if right < n and arr[right] < arr[smallest]:
10            smallest = right
11
12        if smallest == i:
13            return
14
15        arr[i], arr[smallest] = arr[smallest], arr[i]
16        i = smallest
17
18
19def build_min_heap(arr):
20    n = len(arr)
21    for i in range(n // 2 - 1, -1, -1):
22        sift_down(arr, i, n)
23
24build_min_heap(arr)
25print(arr)

This is a real O(n) heap build, not a sequence of O(log n) insertions.

Where The Confusion Comes From

People often mix up two different operations:

• building a heap from an existing array with bottom-up heapify: O(n)
• inserting n items one at a time into an initially empty heap: O(n log n)

Both statements are true, but they describe different algorithms.

Once you distinguish those cases, the contradiction disappears.

Intuition In One Sentence

The root is expensive to heapify, but there is only one root. The leaves are cheap to heapify, and there are many leaves. The cheap nodes dominate the count.

That is why the total is linear even though a single heapify can be logarithmic in the worst case.

Common Pitfalls

• Assuming the cost of building a heap must equal the cost of inserting elements one by one.
• Thinking every node pays the full log n heapify cost during bottom-up construction.
• Forgetting that leaves and near-leaf nodes make up most of the tree.
• Proving the result informally with intuition but not separating the two heap-building algorithms.
• Using "heapify" and "insert" interchangeably even though they are different operations with different total costs.

Summary

• Building a heap by repeated insertion is O(n log n).
• Building a heap bottom-up from an array is O(n).
• The bottom-up cost is linear because most nodes are near the leaves and have tiny heapify cost.
• The total work is the sum of node heights, not n copies of log n.
• The apparent contradiction disappears once you distinguish the two construction methods.