Trees and heaps

Vocabulary

English	Meaning
binary search tree/ˈbaɪnəri sɜːtʃ triː/	A binary tree ordered so keys in the left subtree precede the node and keys in the right follow it.
heap/hiːp/	A tree-based structure satisfying an ordering rule between each parent and its children.
min-heap	A heap in which every parent is no greater than its children, placing a minimum at the root.

Order invariant, complete shape

A binary search tree keeps left subtree below node below right subtree: inserting $50, 30, 70, 20, 40, 60, 80$ builds a perfect tree of height $2$, and the inorder walk reads $20, 30, 40, 50, 60, 70, 80$ — sorted by construction.
A heap is a complete tree stored in an array: children of index $i$ sit at $2i+1$ and $2i+2$. A min-heap keeps every parent at or below its children, so the minimum lives at index $0$.

{exercise:uni-cs0504-shapes}

Practice

In a heap stored as an array, the children of index i sit at —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

A perfect tree of height $h$ holds $2^{h+1} - 1$ nodes: $7$ at $h = 2$, $15$ at $h = 3$, $31$ at $h = 4$ — so balanced $n$ needs height $\lfloor \log_2 n \rfloor$, and every root-to-leaf walk pays it.
Skew breaks the deal: inserting sorted keys $1, 2, 3, 4$ makes a chain of height $3 = n - 1$, $O(n)$ search — the reason AVL and red-black trees rotate to stay logarithmic.

{exercise:uni-cs0504-height}

Practice

A perfect tree of height 3 holds —

Difficulty 1/5 · 100 coins + a small bonus on first completion today

BST search $40$: compare $50$ (go left), $30$ (go right), $40$ — found in $3$ comparisons on $7$ nodes. Insert $35$ hangs it left of $40$; inorder still reads sorted.
Min-heap by inserting $5, 3, 8, 1$: $3$ sifts up over $5$; $1$ sifts up over $5$ then $3$; the array reads $[1, 3, 8, 5]$ — parent at or below children everywhere. heapq.heapify builds a whole array in $O(n)$ by sifting down from the middle.