Building a Heap in Linear Time

Naive Build: $\Theta(n \log n)$

Inserting $n$ elements one by one, each costing $O(\log n)$, gives $\Theta(n \log n)$ total. This is the obvious approach but not optimal.

Linear-Time Build: Bottom-Up Heapify

A more efficient method calls Max-Heapify on all non-leaf nodes, working bottom-up from $\lfloor n/2 \rfloor$ down to 1:

Build-Max-Heap(A):
  A.heap_size = A.length
  for i = floor(A.length / 2) downto 1:
    Max-Heapify(A, i)

The key insight: leaves (indices $\lfloor n/2 \rfloor + 1$ to $n$) are already 1-element max-heaps, so they need no work. Starting from the last non-leaf node and working upward ensures that when Max-Heapify is called on node $i$, both subtrees of $i$ are already valid heaps.

Correctness

Loop invariant: At the start of each iteration, every node index $> i$ is the root of a valid max-heap.

• Initialisation ($i = \lfloor n/2 \rfloor$): All nodes $> \lfloor n/2 \rfloor$ are leaves, trivially heaps.
• Maintenance: Max-Heapify fixes node $i$; after the call, $i$ is also a heap root. Moving to $i-1$ preserves the invariant.
• Termination ($i = 0$): All nodes, including the root (index 1), are valid heaps.

Analysis: Why $O(n)$

The cost of Max-Heapify at node $i$ is proportional to the height of node $i$, i.e. the number of levels below it. At level $h$ from the bottom (height $h$), there are at most $\lceil n / 2^{h+1} \rceil$ nodes, and each Max-Heapify costs $O(h)$. Summing over all levels:

$T(n) \le \sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil \cdot c h \le c \cdot \frac{n}{2} \sum_{h=0}^{\infty} \frac{h}{2^{h-1}}$

The infinite sum converges: $\sum_{h=0}^{\infty} h/2^{h} = 2$. Therefore:

$T(n) = O(n)$

Concrete Calculation

For $n = 15$ (a perfect heap), the tree has 4 levels:

Level (from leaf)	Height $h$	Nodes at this level	Work per node	Total work
0 (leaves)	0	8	0	0
1	1	4	$c$	$4c$
2	2	2	$2c$	$4c$
3 (root)	3	1	$3c$	$3c$

Total: $11c$, whilst $n \log n$ would be $15 \times 3.9c \approx 59c$. The linear-time build is substantially faster.

Step-by-Step Example

Input: $A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]$ ($n=10$)

First non-leaf: $\lfloor 10/2 \rfloor = 5$, value $16$.

Initial array as tree:          After Build-Heap (final):
          4                                 16
      /       \                          /      \
     1         3                       14        10
   /   \     /   \                   /   \     /    \
  2    16   9     10                8     7   9      3
 / \   /                          / \   /
14  8 7                          2   4  1

Step	$i$	Action	Key effect
1	5	Max-Heapify on node with value 16	Already a heap (16 > 7)
2	4	Max-Heapify on node with value 2	Swap 2 with 14; $[14, 8]$ heap
3	3	Max-Heapify on node with value 3	Swap 3 with 10; $[10, 9]$ heap
4	2	Max-Heapify on node with value 1	Swap 1 with 16, then 1 with 7; heap
5	1	Max-Heapify on node with value 4	Swap 4 with 16, then 4 with 14, then 4 with 8

Final heap: $[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$.

Summary

Aspect	Detail
Naive build	Insert $n$ elements: $\Theta(n \log n)$
Efficient build	Bottom-up heapify: $\Theta(n)$
Starting index	$\lfloor n/2 \rfloor$ (last non-leaf)
Why $O(n)$	Most nodes (leaves) cost $O(0)$; higher nodes are few
Series sum	$\sum h / 2^{h}$ converges to 2
Key insight	Work is proportional to height, not depth