Heap — max-heap and min-heap properties

WHAT is a heap?

HOW we store it: the array trick

Formula Index relations (0-based array of size

$n$ ) Derive them from the level-order layout. Number nodes $0,1,2,\dots$ top-to-bottom, left-to-right. A node at level $\ell$ from the left occupies index $i$ . Its two children are the next two "slots" two levels of fan-out away. Working out the counting: $\text{left}(i) = 2i+1, \qquad \text{right}(i) = 2i+2, \qquad \text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor$

Derivation of $2i+1$ : Index $i$ has $i$ nodes before it ( $0..i-1$ ). Each of those $i$ nodes contributes 2 child-slots, so $2i$ child-slots come before node $i$ 's children. The root itself sits at index 0, occupying 1 slot, hence the children of node $i$ start at $2i+1$ . Right child is the next slot, $2i+2$ .

Parent: invert it. From $\text{child} = 2i+1$ or $2i+2$ solve for $i$ : both give $i = \lfloor (\text{child}-1)/2 \rfloor$ .

Figure — Heap — max-heap and min-heap properties

Height and why operations are $O(\log n)$

Worked examples

Recall

Recall Active recall (cover the answers)

What two properties define a heap? → shape (complete tree) + heap-order (parent vs child).
Max-heap root is? → the maximum. Min-heap root? → the minimum.
Are siblings ordered? → No.
0-based children of $i$ ? → $2i+1, 2i+2$ . Parent? → $\lfloor(i-1)/2\rfloor$ .
Height of $n$ -node heap? → $\lfloor\log_2 n\rfloor$ .
Why can't you search a heap in $O(\log n)$ like a BST? → only ancestor–descendant order, siblings unordered.

Recall Feynman: explain to a 12-year-old

Imagine a pyramid of people where every boss is taller than the people directly under them. The tallest person is always at the very top — you can see them instantly. But two people side-by-side might be any heights; we never compare them. When a new person joins, they stand at the next empty spot at the bottom, then keep swapping upward with their boss until they find someone taller above them. That swapping is short because the pyramid is wide and not very tall — so it's always quick.

Connections

Priority Queue — the main use of heaps (insert + extract-min/max).
Heapsort — build-heap then repeatedly extract the root.
Complete Binary Tree — the shape property's foundation.
Binary Search Tree — contrast: BST orders siblings, heap does not.
Build-Heap (Heapify) O(n) — bottom-up sift-down.
Big-O Notation — why $O(\log n)$ per operation.

What two properties must every heap satisfy?

Shape (complete binary tree, last level filled left-to-right) and heap-order (parent vs child relation).

In a max-heap, where is the maximum element?

At the root (index 0).

In a min-heap, where is the minimum element?

At the root (index 0).

Are sibling nodes ordered in a heap?

No — only ancestor–descendant pairs are ordered; siblings can be in any order.

0-based: indices of left and right children of node i?

2i+1 and 2i+2.

0-based: index of the parent of node i?

floor((i-1)/2).

What is the height of a heap with n nodes?

floor(log2(n)).

Why is insert/extract O(log n) in a heap?

Sift-up/sift-down walks at most one root-to-leaf path of length = height = O(log n).

Why can't a heap be searched in O(log n) like a BST?

Siblings are unordered, so you can't discard half the tree by comparison.

When inserting, where does the new element go first and why?

At the next free leaf (last array slot) to preserve the complete-tree shape, then sift up.

In max-heapify (sift-down), do you swap with the larger or smaller child, and why?

The larger child, so the new parent dominates the other child too, keeping the max-heap property.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, heap ek special binary tree hai jisme do rules hamesha lagte hain. Pehla shape rule: tree complete hona chahiye — har level pura bhara ho, sirf last level adhura ho sakta hai aur woh bhi left se right fill hota hai. Doosra order rule: max-heap me har parent apne children se bada ya barabar hota hai (sabse bada element top pe), aur min-heap me parent chhota ya barabar hota hai (sabse chhota top pe). Bas yahi ek local rule poore tree pe lagta hai.

Sabse important baat: heap me siblings ka koi order nahi hota. Bas ancestor aur descendant compare hote hain. Isiliye heap ko BST ki tarah O(log n) me search nahi kar sakte — heap sirf ek hi sawaal fast answer karta hai: "sabse bada/chhota kaun hai?" — woh root pe O(1) me mil jata hai.

Storage ka jugaad mast hai: kyunki tree complete hai, koi gap nahi hota, isliye hum pointers ki jagah simple array use karte hain. Index $i$ ke children $2i+1$ aur $2i+2$ pe hote hain, parent $\lfloor(i-1)/2\rfloor$ pe. Tree ki height hamesha $\lfloor\log_2 n\rfloor$ rehti hai, isliye insert (sift-up) aur delete (sift-down) dono $O(\log n)$ me ho jate hain — bas ek hi path top se bottom tak chalte hain.

Yeh cheez priority queue aur heapsort ke liye backbone hai. Jab bhi tumhe baar-baar "sabse urgent/sabse bada/sabse chhota nikalo" karna ho, heap best choice hai. Rule yaad rakho: max-heap me "Mom is the eXtreme" (parent bada), min-heap me "smallest swims up" (chhota upar).

Heap — max-heap and min-heap properties

WHAT is a heap?

HOW we store it: the array trick

Height and why operations are $O(\log n)$

Worked examples

Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections