Heap operations — insert O(log n), extract-max - min O(log n), decrease-key

The two repair primitives (everything is built from these)

decrease-key (min-heap) / increase-key (max-heap) — $O(\log n)$

Common mistake Steel-manned errors

❌ "extract-max should swap the root with the largest child, not the last leaf." Why it feels right: the largest child does look like the natural successor. Fix: if you promote a child you leave a hole in the middle → tree no longer complete → array indexing breaks. Always move the last element up first, then sift-down.

❌ "decrease-key on a min-heap needs sift-down." Why it feels right: "decrease" sounds like "go down." Fix: a smaller value belongs higher (closer to root in a min-heap), so it must climb — use sift-up.

❌ "parent(i) = i/2 in 0-indexed arrays." Feels right from 1-indexed textbooks. Fix: 0-indexed parent is $\lfloor(i-1)/2\rfloor$ . Check $i=2$ : $i/2=1$ wrong, $(i-1)/2=0$ ✓.

❌ "Heaps are sorted." Feels right because the max is at front. Fix: siblings have no order between them; only the parent–child chain is ordered.

Cost summary (Forecast-then-Verify)

Operation	Steps	Time
peek max/min	read $A[0]$	$O(1)$
insert	append + sift-up	$O(\log n)$
extract-max/min	swap last→root, sift-down	$O(\log n)$
decrease/increase-key	update + sift-up	$O(\log n)$
build-heap (bonus)	sift-down from $n/2-1$ down to 0	$O(n)$

What is the heap property of a max-heap?

Every parent ≥ both its children (the root is the maximum).

0-indexed: children of node i?

left = 2i+1, right = 2i+2.

0-indexed: parent of node i?

floor((i-1)/2).

Insert algorithm in a heap?

Append new key at index n (keeps tree complete), then sift-up to restore property. O(log n).

Why is insert O(log n) not O(n)?

sift-up swaps along a single path of length ≤ height = floor(log2 n).

extract-max steps?

Save A[0]; move last element to root; shrink size; sift-down(0); return saved max.

Why move the LAST element to the root in extract?

It preserves completeness in O(1); promoting a child would leave a hole and break array indexing.

decrease-key on a min-heap uses which primitive?

sift-up — a smaller value belongs higher up.

increase-key on a max-heap uses which primitive?

sift-up — a larger value belongs higher up.

Why is peek O(1) but extract O(log n)?

Peek just reads A[0]; extract must rebalance one root-to-leaf path.

Are siblings ordered in a heap?

No — only the parent–child chain is ordered; heaps are not fully sorted.

Time to build a heap from an array?

O(n) via sift-down from index n/2-1 down to 0.

Recall Feynman: explain to a 12-year-old

Imagine a pyramid of people where every boss stands above and is taller than the two people below them. The tallest person is always on top, so finding the tallest is instant. When a new person joins, they stand at the next open spot at the bottom and keep swapping up with their boss while they're taller — they climb only as high as they deserve. When the top person leaves, we pull the very last person up to the top (so no gaps), then let them sink down by trading places with their tallest kid until everyone above is taller again. Each climb or sink is just one straight line down the pyramid, and the pyramid is short (about $\log n$ floors), so it's fast.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Heap ek aisa array hai jo andar se ek "almost complete" binary tree jaisa behave karta hai. Iska sirf ek hi rule hota hai: max-heap mein har parent apne dono children se bada (≥) hota hai, aur min-heap mein chhota (≤). Isiliye sabse bada (ya chhota) element hamesha root par, yaani index 0 par milta hai — isko padhna $O(1)$ . Pointers ki zaroorat nahi, kyunki index se hi navigate karte hain: children = $2i+1, 2i+2$ aur parent = $\lfloor(i-1)/2\rfloor$ .

Do hi basic moves yaad rakho. sift-up: agar koi node apni jagah se zyada bada ho gaya, to parent ke saath swap karke upar chadho. sift-down: agar root ki jagah chhota element aa gaya, to bade child ke saath swap karke neeche jao. Bas itna hi. insert mein naya element sabse aakhri khaali slot (index $n$ ) par daalte hain taaki tree complete rahe, fir sift-up. extract-max mein root ko nikaalte hain, last wala element root par laate hain (taaki gap na bane), fir sift-down. Dono ek hi root-to-leaf path par kaam karte hain, jiska length $\log n$ hai — isliye $O(\log n)$ .

decrease-key Dijkstra aur Prim mein bahut use hota hai. Min-heap mein kisi node ki value ghata di, to wo chhoti ho gayi, matlab usko upar jaana chahiye — isliye sift-up lagao, sift-down nahi. Yaad rakhna: jab bhi value "favored end" (max-heap mein bada, min-heap mein chhota) ki taraf jaati hai, wo upar udti hai. Common galti: extract mein root ko bade child se swap karna — galat, isse beech mein hole ban jaata hai aur tree incomplete ho jaata hai. Hamesha last element ko upar lao, phir sift-down.

Heap operations — insert O(log n), extract-max - min O(log n), decrease-key

WHAT is a heap (definition)

The two repair primitives (everything is built from these)

sift-up (bubble-up)

sift-down (heapify-down)

insert — $O(\log n)$

extract-max — $O(\log n)$

decrease-key (min-heap) / increase-key (max-heap) — $O(\log n)$

Cost summary (Forecast-then-Verify)

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections