0-Indexed vs 1-Indexed Implicit Heap Arithmetic & $d$-Ary Generalization
Every heap maintains two simultaneous invariants: the Shape Property (the tree is a complete $d$-ary tree filled left-to-right on the bottom level, mapping bijectively to contiguous indices $0 \dots N-1$) and the Heap Order Property (every node's key is $\le$ its children's keys in a Min-Heap, or $\ge$ in a Max-Heap).
- 0-Indexed Binary Heap ($d = 2$): $\text{parent}(i) = (i - 1) \gg 1$, $\text{left}(i) = (i \ll 1) + 1$, $\text{right}(i) = (i \ll 1) + 2$. All indices $\ge \lfloor N/2 \rfloor$ are leaves.
- 1-Indexed Binary Heap ($d = 2$, indices $1 \dots N$): $\text{parent}(i) = i \gg 1$, $\text{left}(i) = i \ll 1$, $\text{right}(i) = (i \ll 1) | 1$. Wasting index 0 eliminates the $-1$ and $+1$ offsets in tight inner loops.
- 0-Indexed $d$-Ary Heap ($d = 4$ or $d = 8$): $\text{parent}(i) = \lfloor(i - 1)/d\rfloor$, and the $k$-th child ($0 \le k < d$) is $d \cdot i + 1 + k$. Increasing branching factor from $2$ to $d=4$ halves tree height ($\log_4 N = \frac{1}{2}\log_2 N$), cutting
siftUpwork by $50\%$ while keeping all 4 siblings inside a single 64-byte CPU cache line!
| Operation | Binary Heap ($d = 2$) | $d$-Ary Heap ($d = 4$) | Comparisons / Memory Transfers |
|---|---|---|---|
peekMin() / peekMax() |
O(1) | O(1) | Read $A[0]$ (always L1 cache hot) |
push(x) / decreaseKey(i, x) (siftUp) |
O(log₂ N) | O(log_d N) | 1 comparison per level ($d=4$ halves levels!) |
popMin() (siftDown) |
2 log₂ N cmps | d log_d N cmps | $d=4$: $4 \log_4 N = 2 \log_2 N$ cmps, $50\%$ fewer cache misses! |
Floyd's Bottom-Up buildHeap(A) |
O(N) (≤ 2N cmps) | O(N) | Linear scan from $\lfloor N/d \rfloor - 1$ down to $0$ |
Theorem (Floyd, 1964): Bottom-Up Build-Heap Executes at Most $N - s_2(N)$ Sift Steps ($le 2N$ Comparisons)
In an $N$-element binary heap, there are at most $\lceil N / 2^{h+1} \rceil$ nodes of height $h$ (distance $h$ from the leaves). Calling siftDown on a node at height $h$ performs at most $h$ swaps (and $2h$ key comparisons). Summing the maximum number of swaps over all heights $h \ge 0$:
$$S(N) = \sum_{h=0}^{\lfloor \log_2 N \rfloor} \left\lceil \frac{N}{2^{h+1}} \right\rceil h \le \frac{N}{2} \sum_{h=1}^{\infty} \frac{h}{2^{h-1}}$$
Differentiating the geometric series $\sum_{h=0}^{\infty} x^h = \frac{1}{1-x}$ gives $\sum_{h=1}^{\infty} h x^{h-1} = \frac{1}{(1-x)^2}$. Substituting $x = 1/2$ yields $\sum_{h=1}^{\infty} \frac{h}{2^h} = \frac{1/2}{(1 - 1/2)^2} = 2$. More precisely, each node at height $h$ adds $h$ to the sum, yielding the exact closed form $S(N) = N - s_2(N)$ swaps, where $s_2(N)$ is the number of 1-bits in the binary representation of $N$ (__builtin_popcount(N)). Since each swap requires 2 comparisons, total comparisons are strictly bounded by $2(N - s_2(N)) < 2N = \Theta(N)$.
Observe how implicit array indices (parent = ⌊(i−1)/d⌋, child_k = d·i+k) eliminate pointer overhead, why Floyd’s bottom-up siftDown sums ∑ 2^(h−k)·k ≤ 2N work, and how an Indexed PQ maintains pos[id] ⇄ heap[i].
Invariant & State
Hardware Reality: Why 4-Ary Heaps Outperform Binary Heaps by 1.5x–2x
Notice a remarkable mathematical coincidence at $d = 4$: during siftDown, a binary heap compares 2 children per level across $\log_2 N$ levels, performing $2 \log_2 N$ comparisons. A 4-ary heap compares 4 children per level across $\log_4 N = \frac{1}{2}\log_2 N$ levels, performing $4 \cdot \frac{1}{2}\log_2 N = 2 \log_2 N$ comparisons—the exact same number of comparisons as a binary heap, while cutting the number of vertical pointer-striding cache line misses in half! Furthermore, the 4 children $A[4i+1 \dots 4i+4]$ sit contiguously in RAM, allowing a single 64-byte L1 cache line fetch and SIMD horizontal minimum instruction to pick the smallest child in one cycle.
Implementation: Zero-Swap Hole-Sinking Floyd Binary Heap
Standard textbook siftDown performs a 3-assignment std::swap at every level. Production implementations (such as libc++ std::make_heap) use Floyd's hole-sinking optimization: save the displaced element $v = A[i]$ in a register, shift winning children upward with a single assignment per level, and write $v$ once into its final resting hole.
// C++20: Floyd's O(N) Build-Heap with Hole-Sinking (1 Assignment per Level Instead of 3)
#include <vector>
#include <utility>
template <typename T>
void siftDown(std::vector<T>& a, size_t i, size_t n) {
T target = std::move(a[i]);
size_t hole = i;
while (true) {
size_t left = (hole << 1) + 1;
if (left >= n) break;
size_t bestChild = left;
if (left + 1 < n && a[left + 1] < a[left]) {
bestChild = left + 1;
}
if (!(a[bestChild] < target)) break;
a[hole] = std::move(a[bestChild]); // Single move upward; no 3-way swap!
hole = bestChild;
}
a[hole] = std::move(target);
}
template <typename T>
void floydBuildMinHeap(std::vector<T>& a) {
const size_t n = a.size();
if (n <= 1) return;
for (size_t i = n / 2; i-- > 0; ) {
siftDown(a, i, n);
}
}Failure Modes & Adversarial Pitfalls
- Searching or Deleting Arbitrary Elements in a Unindexed Heap is $O(N)$, Not $O(\log N)$: A Min-Heap only orders ancestors relative to descendants; it tells you nothing about whether an arbitrary key $x$ resides in the left subtree or right subtree. Finding an element by value in an unindexed heap requires an $O(N)$ linear scan, and finding the maximum element requires scanning all $\lceil N/2 \rceil$ leaves!
- Integer Overflow on
2 * i + 1: In 32-bit index arithmetic, if $N > 2^{30}$, computing2 * i + 1overflows signed 32-bitint. Always use unsigned 64-bitsize_tfor heap index calculations.