Difficulty: Intermediate to Advanced | Prerequisites: Binary trees, BSTs, AVL trees, Big-O analysis
This section covers three structures that solve quite different problems but share a theme: clever structural invariants that guarantee performance. B-trees extend balanced search trees for systems where disk access is expensive. Heaps provide O(1) access to the minimum (or maximum) element. Disjoint sets efficiently track which elements belong to the same group, which becomes critical for graph algorithms like Kruskal's MST. The analysis of disjoint sets with union by rank and path compression introduces the inverse Ackermann function, one of the slowest-growing functions you will encounter.
TL;DR: B-trees keep trees short and wide for disk efficiency. Heaps are complete binary trees that let you extract the min/max in O(log n). Disjoint sets track connected components with near-constant-time operations using union by rank and path compression.
B-tree
A self-balancing search tree where each node can hold multiple keys and have multiple children. Designed to minimise disk reads by keeping the tree very short (low height). In simple terms, a BST on steroids that branches many ways instead of just two.
Order (of a B-tree)
A B-tree of order m allows each node to have at most m children and m - 1 keys. Each internal node (except the root) must have at least ceil(m/2) children.
Heap
A complete binary tree where the value of each node satisfies a heap property relative to its children. In a min-heap, every parent is smaller than its children; in a max-heap, every parent is larger.
Heap property (min-heap)
For every node, node.value ≤ child.value. The minimum element is always at the root.
Heapify down (percolate down, sift down)
After removing the root, move the replacement element down the tree by swapping it with its smaller child until the heap property is restored.
Heapify up (percolate up, sift up)
After inserting at the bottom, move the new element up by swapping it with its parent until the heap property is restored.
Build heap
Constructing a heap from an unsorted array in O(n) time by applying heapify-down from the last internal node up to the root.
Priority queue
An ADT that supports insert and extract-min (or extract-max). A heap is the standard implementation.
Disjoint set (union-find)
A data structure that tracks a collection of non-overlapping sets. Supports two operations: find (which set does this element belong to?) and union (merge two sets).
Union by rank
When merging two sets, attach the shorter tree under the root of the taller tree to keep the combined tree shallow.
Union by size
A variant where you attach the smaller set under the larger set's root.
Path compression
During a find operation, make every node on the path point directly to the root. This flattens the tree for future operations.
Inverse Ackermann function, α(n)
The amortised time per operation for disjoint sets with union by rank and path compression. It grows so slowly that for all practical input sizes (up to 2^65536), α(n) ≤ 4. Effectively constant.
kD-tree
A space-partitioning data structure for organising points in k-dimensional space. Each level of the tree splits along a different dimension. Used for nearest-neighbour searches.
Why B-trees exist: disk reads are expensive. A B-tree of order m stores up to m - 1 keys per node, so a single disk read retrieves many keys. This keeps the tree height very small.
Structure rules (order m)
Every node has at most m children
Every internal node (except root) has at least ceil(m/2) children
The root has at least 2 children (unless it is a leaf)
All leaves are at the same depth
A node with k children holds k - 1 keys, in sorted order
Search: similar to BST, but at each node you search through multiple keys to decide which child to follow
Insertion
Find the correct leaf and insert the key in sorted order
If the leaf overflows (more than m - 1 keys), split it into two nodes and push the middle key up to the parent
Splitting may cascade up to the root; if the root splits, a new root is created (this is the only way the tree grows taller)
Deletion
If the key is in a leaf, remove it directly
If in an internal node, replace with the predecessor or successor (from a leaf), then delete from the leaf
If a node underflows (fewer than ceil(m/2) - 1 keys), either borrow from a sibling or merge with a sibling
Height of a B-tree: for n keys and order m, the height is O(log_m n). With m = 1000, a tree holding a billion keys is only about 3 levels deep.
Shape property: a heap is a complete binary tree (every level filled except possibly the last, which is filled left to right)
Array representation: because the shape is fixed, a heap maps neatly onto an array
Root is at index 1 (or 0, depending on convention)
For a node at index i: left child at 2i, right child at 2i + 1, parent at floor(i/2)
No pointers needed; the array indices encode the tree structure
Insert: place the new element at the next available position (end of array), then heapify up. O(log n)
Remove min (extract-min): swap the root with the last element, remove the last element, then heapify down from the root. O(log n)
Build heap (Floyd's algorithm)
Start with an unsorted array
From the last internal node (index n/2) down to index 1, apply heapify-down
Runs in O(n), not O(n log n), because most nodes are near the bottom and heapify-down is cheap for them
The proof uses the fact that the sum of heights across all nodes is O(n)
Heap sort
Build a max-heap in O(n)
Repeatedly extract the max (swap with last, shrink heap, heapify down)
Total: O(n log n), in-place, not stable
Problem: given n elements, group them into sets. Support two operations:
Find(x): return the representative (root) of the set containing x
Union(x, y): merge the sets containing x and y
Naive implementation (array of up-trees)
Each element points to its parent; roots point to themselves
Find follows parent pointers to the root: O(h)
Union makes one root point to the other
Union by rank
Each root tracks its rank (an upper bound on height)
When unioning, attach the lower-rank tree under the higher-rank root
If ranks are equal, pick either and increment the new root's rank
Ensures height is at most O(log n)
Path compression
During find, set every node on the path to point directly to the root
Dramatically flattens the tree for future operations
Can be implemented recursively or iteratively
Combined performance: with both union by rank and path compression, m operations on n elements take O(m · α(n)), where α is the inverse Ackermann function. For all practical purposes, each operation is O(1).
Purpose: organise points in k-dimensional space for efficient range and nearest-neighbour queries
Construction: at each level, split along a different dimension (cycle through x, y, z, etc.)
At depth d, split on dimension d mod k
Choose the median point along that dimension as the splitting value
Search: similar to BST search but compare different coordinates at each level
Nearest-neighbour search: traverse the tree, pruning branches that cannot contain a closer point than the current best
Time complexity: O(log n) average for balanced kD-trees, O(n) worst case
Heap array indexing (1-based):
Parent of node i: floor(i / 2)
Left child of node i: 2i
Right child of node i: 2i + 1
Build heap time complexity proof (sketch):
Sum of heights = Σ (from h=0 to H) of ceil(n / 2^(h+1)) · h
This sum converges to O(n), not O(n log n), because nodes at greater height are exponentially fewer.
B-tree height:
h ≤ log_{ceil(m/2)} ((n + 1) / 2)
Disjoint sets with union by rank (no path compression):
Find and union are both O(log n).
Disjoint sets with union by rank + path compression:
Amortised O(α(n)) per operation, where α(n) ≤ 4 for any conceivable input size.
B-trees power nearly every database index and file system (ext4, NTFS, HFS+). When you query a database by a key, the index is almost certainly a B-tree or B+ tree. Heaps implement priority queues used in operating system schedulers, Dijkstra's shortest path algorithm, and event-driven simulations. Disjoint sets are used in Kruskal's MST algorithm, image segmentation, and network connectivity analysis.
"Build heap is O(n log n) because you call heapify n times." Each call to heapify-down costs O(h) for that node's height, and most nodes have small height. The total work sums to O(n).
"A heap is a sorted array." A heap only guarantees that the root is the min (or max). The rest of the array is not sorted; siblings have no ordering relationship.
"Union by rank always produces a tree of height exactly log n." Rank is an upper bound on height, especially after path compression has flattened paths. The actual height may be much less.
"B-tree order m means each node has m keys." Each node has at most m - 1 keys and at most m children. The order defines the branching factor, not the key count.
⚠️ Be able to insert into and delete from a B-tree of a given order, showing each split or merge step.
⚠️ Know how to build a heap from an array using Floyd's algorithm and trace the heapify-down steps.
⚠️ Understand why build-heap is O(n), not O(n log n). You may need to argue this with the summation.
⚠️ Be able to trace union-find operations with union by rank and path compression, showing how the tree changes.
⚠️ The difference between union by rank and union by size matters: rank does not decrease with path compression, while the actual height does.
⚠️ kD-tree construction (choosing split dimension and median) and nearest-neighbour pruning logic are testable.
True or false: In a min-heap, the second-smallest element must be a child of the root.
Fill in the blank: A B-tree of order 5 allows each node to have at most ______ keys.
True or false: Path compression changes the rank of the root.
Fill in the blank: In a heap stored in a 1-indexed array, the parent of node at index 10 is at index ______.
True or false: All leaves in a B-tree are at the same depth.
Answers: 1. True (it must be one of the root's children). 2. 4. 3. False (rank is unchanged; only actual heights change). 4. 5. 5. True.
Q: Insert the values [4, 10, 3, 5, 1] into an empty min-heap. Show the heap after each insertion.
A: Insert 4: [4]. Insert 10: [4, 10]. Insert 3: [3, 10, 4] (3 heapifies up past 4). Insert 5: [3, 5, 4, 10] (5 heapifies up past 10). Insert 1: [1, 3, 4, 10, 5] (1 heapifies up past 5 then past 3).
Q: Explain why a B-tree of order 1001 holding one billion keys has a height of at most 3.
A: Each node holds up to 1000 keys. The root has up to 1001 children, each of those has up to 1001 children, and so on. At height 3, the tree can hold 1001^3 ≈ 10^9 leaf pointers, which is enough for one billion keys.
Q: After performing find(x) with path compression, what does the tree look like?
A: Every node on the path from x to the root now points directly to the root. The next find on any of these nodes will be O(1).
Q: Can you use a max-heap as a min-priority queue? How?
A: Yes, by negating all keys before insertion and negating again on extraction. A max-heap on negated values behaves as a min-heap on the original values. This is a common trick when only a max-heap implementation is available.
B-trees connect to the balanced BST material from Weeks 5 and 6 by generalising the balancing idea to multi-way trees. Heaps are the engine behind Dijkstra's algorithm and Prim's MST algorithm (Weeks 10 and 11). Disjoint sets are essential for Kruskal's MST algorithm. kD-trees connect to the broader theme of spatial data structures and reappear in computational geometry and machine learning (k-nearest-neighbours).
B-tree, B+ tree, order, branching factor, split, merge, heap, min-heap, max-heap, binary heap, priority queue, heapify, heapify up, heapify down, percolate, sift, build heap, Floyd's algorithm, heap sort, disjoint set, union-find, union by rank, union by size, path compression, inverse Ackermann, amortised, up-tree, kD-tree, k-dimensional tree, nearest neighbour, range search, CS 225, data structures, UIUC