Heap data structures are the backbone of efficient priority queue implementations, powering everything from graph algorithms to real-time scheduling systems. A heap is a complete binary tree stored compactly as an array, where parent-child relationships are encoded by index arithmetic rather than pointers — making operations cache-friendly and memory-efficient. The key insight practitioners need is that heaps do not maintain full sort order; they only guarantee the root holds the extreme element, which is enough for priority-driven processing in O(log n) per operation. The right heap variant — binary, Fibonacci, pairing, or d-ary — depends on whether you need fast decrease-key (graph algorithms) or fast bulk construction (sorting), and understanding that trade-off unlocks a whole class of optimal algorithms.
What This Cheat Sheet Covers
This topic spans 13 focused tables and 91 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Binary Heap — Structure and Array Representation
A binary heap stores a complete binary tree implicitly in an array with no pointers needed. Knowing the index formulas is essential for implementing any heap from scratch and for reasoning about cache behavior.
| Concept | Example | Description |
|---|---|---|
heap = [1, 3, 6, 5, 9, 8] | • Root at index 0 • level-order traversal fills the array left-to-right | |
parent(i) = (i - 1) // 2 | • Integer division • parent(3) = 1, parent(4) = 1. | |
left(i) = 2*i + 1 | • left(1) = 3• left child of node at index 1 is at index 3. | |
right(i) = 2*i + 2 | • right(1) = 4• right child of node at index 1 is at index 4. | |
n nodes → height \lfloor \log_2 n \rfloor | • All levels fully filled except possibly the last, filled left-to-right • guarantees O(log n) height |