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

Before you can trust the parent note's sift-up, parent(i)=⌊(i-1)/2⌋, and $O(\log n)$ claims, you need to own every piece of notation it throws at you. We build them one at a time, from zero. Nothing is used before it is drawn.

1. What an array actually is (index, A[i])

We count boxes starting at $0$, not $1$. So the first box is $A[0]$, the second is $A[1]$, and so on. This is called 0-indexed, and it is the single most common source of confusion in the parent note — so pin it down now.

2. A tree, a parent, a child, a root, a leaf

In a binary tree, every node has at most two children — a left child and a right child. That is the only shape heaps use.

If you want the full definition of the exact tree shape heaps use, see Complete Binary Tree.

3. The one bridge: array position ⇄ tree position

Here is the magic move. We lay the tree out into the array by reading it top-to-bottom, left-to-right. Root goes in box $0$, its two children in boxes $1$ and $2$, the next level in boxes $3,4,5,6$, and so on.

Two new symbols just appeared — earn them before use:

Let's check the formula against the picture, covering both a left child and a right child:

4. The comparison symbols: $\ge$, $\le$, $>$, $<$

5. Swapping two boxes

6. Reading $O(\log n)$ — what "cost" means

Two ideas hide inside $O(\log n)$. Split them.

7. How it all feeds the topic

This foundation feeds straight into the parent Heap operations note, and from there into Priority Queue, Heapsort, Build-Heap (Heapify), Dijkstra's Algorithm, and Prim's MST. Note that a heap is not a Binary Search Tree — it orders only parent-to-child, not left-to-right.

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, re-read its section above before touching the parent note.