Heaps and Priority Queue Algorithms Cheat Sheet

Updated 2026-05-21

Next Topic: Information Theory Cheat Sheet

🧠Study flashcards on this topic80 cards · spaced repetition→

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, 80 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Binary Heap — Structure and Array RepresentationTable 2: Core Heap Operations and ComplexityTable 3: Build-Heap (Heapify) — Linear Time ConstructionTable 4: Heap SortTable 5: Priority Queue Concepts and ImplementationsTable 6: Top-K Elements PatternsTable 7: Find Median from Data Stream (Two-Heap Pattern)Table 8: Merge K Sorted Lists / ArraysTable 9: Graph Algorithms with HeapsTable 10: Scheduling and Real-World Priority Queue PatternsTable 11: Advanced Heap Variants — Mergeable HeapsTable 12: Heap Complexity Comparison TableTable 13: Common Gotchas and Pitfalls

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

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
Array layout (0-indexed)	`heap = [1, 3, 6, 5, 9, 8]`	• Root at index 0 • level-order traversal fills the array left-to-right
Parent index (0-indexed)	`parent(i) = (i - 1) // 2`	• Integer division • `parent(3) = 1`, `parent(4) = 1`.
Left child index (0-indexed)	`left(i) = 2*i + 1`	• `left(1) = 3` • left child of node at index 1 is at index 3.
Right child index (0-indexed)	`right(i) = 2*i + 2`	• `right(1) = 4` • right child of node at index 1 is at index 4.
Complete binary tree property	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
Heap property (min-heap)	`heap[parent(i)] <= heap[i]` for all i	• Every parent ≤ its children • root holds the minimum.
Heap property (max-heap)	`heap[parent(i)] >= heap[i]` for all i	• Every parent ≥ its children • root holds the maximum.
Space complexity	`O(n)` array of n elements	• No pointer overhead • the only storage is the array itself
Last non-leaf node	`last_non_leaf = n // 2 - 1`	• Index of the last internal node • build-heap iterates from here down to 0.

Table 2: Core Heap Operations and Complexity

The three fundamental operations — insert, extract-min/max, and heapify — are the building blocks for every heap-based algorithm. Understanding when to sift up vs. sift down is the key to implementing them correctly.

Operation	Example	Description
sift-up (bubble-up / percolate-up)	`while i > 0 and heap[parent(i)] > heap[i]:` `swap(heap, i, parent(i)); i = parent(i)`	• Restores heap property upward after insertion • swaps node with parent while parent is larger (min-heap). O(log n).

The rest of this section is part of the full cheat sheet

Table 3: Build-Heap (Heapify) — Linear Time Construction

Build-heap transforms an arbitrary array into a valid heap in O(n) time — a non-obvious result that is crucial for heap sort and bulk initialization. The key is iterating sift-down from the last internal node upward, not repeatedly inserting elements.

Concept	Example	Description
build-heap (Floyd's algorithm)	`for i in range(n//2 - 1, -1, -1):` `sift_down(arr, i, n)`	Iterates sift-down on all non-leaf nodes from last to root. O(n) — not O(n log n).

The rest of this section is part of the full cheat sheet

Table 4: Heap Sort

Heap sort is a two-phase O(n log n) in-place algorithm invented alongside the binary heap by J. W. J. Williams in 1964. It builds a max-heap then repeatedly extracts the maximum, achieving guaranteed O(n log n) with O(1) auxiliary space.

Concept	Example	Description
Heap sort algorithm	`build_max_heap(arr)` `for i in range(n-1, 0, -1):` `swap(arr[0], arr[i])` `heapify(arr, i, 0)`	Phase 1: build max-heap O(n). Phase 2: n-1 swaps + sift-down each O(log n). Total O(n log n).

The rest of this section is part of the full cheat sheet

Table 1: Binary Heap — Structure and Array Representation

Concept	Example	Description
Array layout (0-indexed)	`heap = [1, 3, 6, 5, 9, 8]`	• Root at index 0 • level-order traversal fills the array left-to-right
Parent index (0-indexed)	`parent(i) = (i - 1) // 2`	• Integer division • `parent(3) = 1`, `parent(4) = 1`.
Left child index (0-indexed)	`left(i) = 2*i + 1`	• `left(1) = 3` • left child of node at index 1 is at index 3.
Right child index (0-indexed)	`right(i) = 2*i + 2`	• `right(1) = 4` • right child of node at index 1 is at index 4.
Complete binary tree property	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
Heap property (min-heap)	`heap[parent(i)] <= heap[i]` for all i	• Every parent ≤ its children • root holds the minimum.
Heap property (max-heap)	`heap[parent(i)] >= heap[i]` for all i	• Every parent ≥ its children • root holds the maximum.
Space complexity	`O(n)` array of n elements	• No pointer overhead • the only storage is the array itself
Last non-leaf node	`last_non_leaf = n // 2 - 1`	• Index of the last internal node • build-heap iterates from here down to 0.

Table 2: Core Heap Operations and Complexity

Operation	Example	Description
sift-up (bubble-up / percolate-up)	`while i > 0 and heap[parent(i)] > heap[i]:` `swap(heap, i, parent(i)); i = parent(i)`	• Restores heap property upward after insertion • swaps node with parent while parent is larger (min-heap). O(log n).

Table 3: Build-Heap (Heapify) — Linear Time Construction

Concept	Example	Description
build-heap (Floyd's algorithm)	`for i in range(n//2 - 1, -1, -1):` `sift_down(arr, i, n)`	Iterates sift-down on all non-leaf nodes from last to root. O(n) — not O(n log n).

Table 4: Heap Sort

Concept	Example	Description
Heap sort algorithm	`build_max_heap(arr)` `for i in range(n-1, 0, -1):` `swap(arr[0], arr[i])` `heapify(arr, i, 0)`	Phase 1: build max-heap O(n). Phase 2: n-1 swaps + sift-down each O(log n). Total O(n log n).