A heap is just an array we pretend is a complete binary tree. To turn a random array into a valid heap, the naive idea is "insert items one by one" — that's O ( n log n ) O(n \log n) O ( n log n ) start from the bottom of the tree and sift things down . The genius is that most nodes are near the bottom, where sift-down is cheap. The few expensive nodes (near the root) are rare . The cheap-but-numerous vs expensive-but-rare trade-off is exactly why the total cost collapses to ==O ( n ) O(n) O ( n ) O ( n log n ) O(n\log n) O ( n log n )
Definition Build-heap (bottom-up heapify)Given an arbitrary array A[0..n-1] interpreted as a complete binary tree, heapify rearranges it so it satisfies the heap property (for a max-heap: every parent ≥ \ge ≥ siftDown on every non-leaf node, processing nodes from the last internal node up to the root (index 0 0 0
Array ↔ tree index map (0-based):
parent of i i i ⌊ ( i − 1 ) / 2 ⌋ \lfloor (i-1)/2 \rfloor ⌊( i − 1 ) /2 ⌋
left child of i i i 2 i + 1 2i+1 2 i + 1
right child of i i i 2 i + 2 2i+2 2 i + 2
last internal (non-leaf) node: index ⌊ n / 2 ⌋ − 1 \lfloor n/2 \rfloor - 1 ⌊ n /2 ⌋ − 1
⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor - 1 ⌊ n /2 ⌋ − 1 already trivially valid heaps (a single node has no children to violate anything). So there's no point sifting them. The first node that could have a child is the parent of the very last element, which lives at index ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor - 1 ⌊ n /2 ⌋ − 1
siftDown(i) assumes the subtrees rooted at i's children are already valid heaps, and pushes A[i] down until the heap property holds.
siftDown(A, i, n): while True: l = 2*i + 1 r = 2*i + 2 largest = i if l < n and A[l] > A[largest]: largest = l if r < n and A[r] > A[largest]: largest = r if largest == i: break # parent already biggest swap(A[i], A[largest]) i = largest # follow the swap down buildHeap(A, n): for i from floor(n/2)-1 down to 0: siftDown(A, i, n)
upward ?
siftDown(i) needs its children's subtrees to already be heaps. If we go from the bottom up, by the time we reach node i, both its children's subtrees were fixed in earlier iterations. This is a tiny bottom-up dynamic-programming order: solve small subtrees first, combine into bigger ones.
Set-up. A complete binary tree of n n n h = ⌊ log 2 n ⌋ h = \lfloor \log_2 n \rfloor h = ⌊ log 2 n ⌋ node height from the bottom: leaves have height 0 0 0 h h h
Cost of one siftDown. A node at height k k k k k k O ( k ) O(k) O ( k )
Count nodes at each height. In a (near-)complete tree there are at most ⌈ n / 2 k + 1 ⌉ \lceil n / 2^{k+1}\rceil ⌈ n / 2 k + 1 ⌉ k k k
n / 2 k + 1 n/2^{k+1} n / 2 k + 1 n / 2 n/2 n /2 n / 4 n/4 n /4 k k k ≈ n / 2 k + 1 \approx n/2^{k+1} ≈ n / 2 k + 1 exponentially rare .
Sum the total work.
T ( n ) = ∑ k = 0 h n 2 k + 1 ⏟ count ⋅ O ( k ) ⏟ cost = O ( n ∑ k = 0 h k 2 k + 1 ) ≤ O ( n 2 ∑ k = 0 ∞ k 2 k ) . T(n) \;=\; \sum_{k=0}^{h} \underbrace{\frac{n}{2^{k+1}}}_{\text{count}} \cdot \underbrace{O(k)}_{\text{cost}}
\;=\; O\!\left(n \sum_{k=0}^{h} \frac{k}{2^{k+1}}\right)
\;\le\; O\!\left(\frac{n}{2}\sum_{k=0}^{\infty} \frac{k}{2^{k}}\right). T ( n ) = k = 0 ∑ h count 2 k + 1 n ⋅ cost O ( k ) = O ( n k = 0 ∑ h 2 k + 1 k ) ≤ O ( 2 n k = 0 ∑ ∞ 2 k k ) . Now evaluate the key infinite sum. Use the standard identity (derived below):
∑ k = 0 ∞ k x k = x ( 1 − x ) 2 , ∣ x ∣ < 1. \sum_{k=0}^{\infty} k\,x^{k} \;=\; \frac{x}{(1-x)^2}, \qquad |x|<1. k = 0 ∑ ∞ k x k = ( 1 − x ) 2 x , ∣ x ∣ < 1. Plug x = 1 2 x = \tfrac12 x = 2 1
∑ k = 0 ∞ k 2 k = 1 / 2 ( 1 − 1 / 2 ) 2 = 1 / 2 1 / 4 = 2. \sum_{k=0}^{\infty} \frac{k}{2^{k}} = \frac{1/2}{(1-1/2)^2} = \frac{1/2}{1/4} = 2. k = 0 ∑ ∞ 2 k k = ( 1 − 1/2 ) 2 1/2 = 1/4 1/2 = 2. Therefore
T ( n ) ≤ O ( n 2 ⋅ 2 ) = O ( n ) . T(n) \le O\!\left(\frac{n}{2}\cdot 2\right) = \boxed{O(n)}. T ( n ) ≤ O ( 2 n ⋅ 2 ) = O ( n ) .
The series converges to a constant (it doesn't grow with n n n log \log log killed because the expensive nodes are exponentially few. That's why bottom-up build is strictly linear , beating repeated insertion's O ( n log n ) O(n\log n) O ( n log n )
Worked example Example 1 — build a max-heap from[3, 9, 2, 1, 4, 5]
n = 6 n=6 n = 6 = ⌊ 6 / 2 ⌋ − 1 = 2 = \lfloor 6/2\rfloor - 1 = 2 = ⌊ 6/2 ⌋ − 1 = 2 i = 2 , 1 , 0 i = 2,1,0 i = 2 , 1 , 0
Tree (indices): 0=3, 1=9, 2=2, 3=1, 4=4, 5=5.
i=2 (value 2, children idx 5=5): 5>2 → swap. Array: [3,9,5,1,4,2].
Why this step? Node 2's only child (5) is larger, so the parent must take it.
i=1 (value 9, children idx 3=1, 4=4): both smaller → no swap. [3,9,5,1,4,2].
Why this step? 9 already ≥ \ge ≥
i=0 (value 3, children idx 1=9, 2=5): largest is 9 → swap with idx 1. [9,3,5,1,4,2]. Now sift the 3 at idx 1: children idx 3=1, 4=4 → 4 is largest → swap. [9,4,5,1,3,2]. Node now at idx 4 is a leaf → stop.
Why this step? After swapping at the root, the demoted value (3) might still violate the property below, so we keep following it down.
Result: [9,4,5,1,3,2] — valid max-heap (check: 9≥4,5; 4≥1,3; 5≥2 ✓).
Worked example Example 2 — min-heap from[5, 1, 8, 2, 7]
n = 5 n=5 n = 5 = ⌊ 5 / 2 ⌋ − 1 = 1 =\lfloor 5/2\rfloor -1 = 1 = ⌊ 5/2 ⌋ − 1 = 1 i = 1 , 0 i=1,0 i = 1 , 0 ≤ \le ≤
i=1 (value 1, children idx 3=2, 4=7): 1 already smallest → no swap.
i=0 (value 5, children idx 1=1, 2=8): smallest is 1 → swap idx 0,1 → [1,5,8,2,7]. Sift the 5 at idx 1: children idx 3=2, 4=7 → 2 smaller → swap → [1,2,8,5,7]. idx 3 is leaf → stop.
Result: [1,2,8,5,7] ✓ (1≤2,8; 2≤5,7).
Common mistake "Heapify isO ( n log n ) O(n\log n) O ( n log n ) O ( log n ) O(\log n) O ( log n ) Why it feels right: n n n O ( log n ) O(\log n) O ( log n ) n log n n\log n n log n The fix: That bound is loose . It pretends every node sinks the full height. But a height-k k k O ( k ) O(k) O ( k ) half the nodes are leaves costing 0 0 0 ∑ ( n / 2 k + 1 ) ⋅ k \sum (n/2^{k+1})\cdot k ∑ ( n / 2 k + 1 ) ⋅ k O ( n ) O(n) O ( n ) O ( n log n ) O(n\log n) O ( n log n ) true upper bound — it's just not tight .
Common mistake Calling siftDown on leaves / wrong start index.Why it feels right: "Process every node" sounds safe.
The fix: Leaves are already heaps; sifting them is wasted work and indexing children may go out of bounds if not guarded. Always start at ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor - 1 ⌊ n /2 ⌋ − 1
Common mistake Processing top-down (root first).Why it feels right: We read the tree top-to-bottom, so why not fix the root first?
The fix: siftDown(i) requires children's subtrees to already be valid. Going top-down breaks that assumption and produces a non-heap. (If you must go top-down, you need siftUp and the whole thing becomes the slower insertion build.)
Common mistake Insertion build (siftUp for each new element) is "the same thing."
Why it feels right: It also yields a heap.
The fix: siftUp makes leaves (the numerous nodes) travel toward the root — the expensive direction — giving O ( n log n ) O(n\log n) O ( n log n ) siftDown pushes expensive work to the rare tall nodes → O ( n ) O(n) O ( n )
Recall Feynman: explain to a 12-year-oldImagine a tournament bracket drawn as a pyramid of people, biggest-and-strongest should be on top. Most people stand at the bottom rows — there are tons of them, but each only has to wrestle one or two people right above them: cheap. As you go up, there are way fewer people, and only those few have long climbs. Because the crowded bottom is cheap and the tall climbs are rare, the total wrestling is just "about one match per person" — it grows in a straight line with the number of people, not faster.
"Leaves are lazy, roots do the heavy lifting." Start past the leaves (⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor-1 ⌊ n /2 ⌋ − 1 down , go up . And remember the magic number: ∑ k / 2 k = 2 \sum k/2^k = 2 ∑ k / 2 k = 2 O ( n ) O(n) O ( n )
What is the time complexity of bottom-up heapify? O ( n ) O(n) O ( n ) (linear), tighter than the loose
O ( n log n ) O(n\log n) O ( n log n ) bound.
At which index does bottom-up build-heap start? The last internal node,
⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor - 1 ⌊ n /2 ⌋ − 1 (everything after is a leaf).
Why do we process nodes from bottom to top in build-heap? siftDown(i) requires both children's subtrees to already be valid heaps; bottom-up guarantees that ordering.
Cost of siftDown on a node at height k k k O ( k ) O(k) O ( k ) — it can sink at most
k k k levels.
How many nodes are at height k k k About
n / 2 k + 1 n/2^{k+1} n / 2 k + 1 ; tall nodes are exponentially rare.
Which infinite sum proves the O ( n ) O(n) O ( n ) ∑ k = 0 ∞ k / 2 k = 2 \sum_{k=0}^{\infty} k/2^{k} = 2 ∑ k = 0 ∞ k / 2 k = 2 , a constant.
Derive ∑ k x k \sum k x^k ∑ k x k Differentiate
∑ x k = 1 / ( 1 − x ) \sum x^k = 1/(1-x) ∑ x k = 1/ ( 1 − x ) to get
∑ k x k − 1 = 1 / ( 1 − x ) 2 \sum k x^{k-1}=1/(1-x)^2 ∑ k x k − 1 = 1/ ( 1 − x ) 2 , then multiply by
x x x :
∑ k x k = x / ( 1 − x ) 2 \sum k x^k = x/(1-x)^2 ∑ k x k = x / ( 1 − x ) 2 .
Why is insertion-based build O ( n log n ) O(n\log n) O ( n log n ) O ( n ) O(n) O ( n ) siftUp moves the numerous leaves toward the root (expensive direction); siftDown gives the long path only to rare tall nodes.
Children/parent index formulas (0-based)? left
= 2 i + 1 =2i+1 = 2 i + 1 , right
= 2 i + 2 =2i+2 = 2 i + 2 , parent
= ⌊ ( i − 1 ) / 2 ⌋ =\lfloor(i-1)/2\rfloor = ⌊( i − 1 ) /2 ⌋ .
Why are leaves skipped? A single node is already a valid heap; sifting it is wasted work and risks out-of-bounds child access.
Binary Heap — the data structure heapify produces.Heapsort — uses build-heap (O ( n ) O(n) O ( n ) n n n O ( n log n ) O(n\log n) O ( n log n ) Priority Queue — heaps as its standard implementation.Complete Binary Tree — the array↔tree index mapping.Geometric Series / Amortized Analysis — the summation trick behind the linear bound.siftUp vs siftDown — why direction decides complexity.
ensures children heaps first
Array as complete binary tree
Heap property parent >= children
Start at last internal node
Intuition Hinglish mein samjhoDekho, heap ek aisa array hai jise hum mentally ek complete binary tree maan lete hain — parent index i ke children 2i+1 aur 2i+2 par. Ab agar humein random array ko valid heap banana hai, to ek naive tareeka hai: ek-ek element insert karo aur upar sift karo — yeh O ( n log n ) O(n\log n) O ( n log n ) bottom-up heapify : tree ke neeche se shuru karo (index ⌊ n / 2 ⌋ − 1 \lfloor n/2\rfloor - 1 ⌊ n /2 ⌋ − 1 siftDown karo, root tak upar jaate hue.
siftDown(i) ka kaam simple hai: maan lo i ke dono children ke subtrees already valid heap hain; bas A[i] ko neeche tab tak girao jab tak woh apne sabse bade child se bada na ho jaye (max-heap me). Hum upar ki taraf isliye chalte hain kyunki siftDown ko children ke subtrees pehle se theek chahiye — yeh ek mini dynamic-programming order hai: chhote subtrees pehle solve, fir bade.
Asli magic complexity me hai. Logon ko lagta hai n n n O ( log n ) O(\log n) O ( log n ) O ( n log n ) O(n\log n) O ( n log n ) dheela (loose) hai. Sachchai: height k k k O ( k ) O(k) O ( k ) k k k n / 2 k + 1 n/2^{k+1} n / 2 k + 1 kam hote hain. Total cost banta hai n 2 ∑ k / 2 k \frac{n}{2}\sum k/2^k 2 n ∑ k / 2 k 2 par converge ho jaata hai (constant). Isliye total O ( n ) O(n) O ( n ) "leaves lazy hain, root mehnat karta hai" — neeche bahut nodes par kaam sasta, upar mehnga kaam sirf gine-chune nodes par. Heapsort isi O ( n ) O(n) O ( n )
