Trees
Heap Fundamentals
A heap is a complete binary tree stored in an array where every parent is smaller (min-heap) or larger (max-heap) than its children. This gives O(1) access to the extreme element and O(log n) insert/extract. Heaps power Java’s PriorityQueue, Python’s heapq, and are the engine behind Dijkstra’s algorithm, top-K problems, and median-finding.
01
Section One · Foundation
What is Heap?
A heap has two properties: (1) it is a complete binary tree — every level is full except possibly the last, which fills left to right; and (2) it satisfies the heap property — every parent ≤ children (min-heap) or ≥ children (max-heap). The root always holds the min/max, giving O(1) peek. Because it’s complete, we store it in a flat array: parent at i, children at 2i+1 and 2i+2.
Two flavours:
Min-Heap
Smallest on Top
Parent ≤ children. Root = global minimum. Java PriorityQueue and Python heapq are min-heaps by default.
- Dijkstra’s shortest path
- Merge K sorted lists
- K-th largest (min-heap of size K)
Max-Heap
Largest on Top
Parent ≥ children. Root = global maximum. In Java use Comparator.reverseOrder(); in Python negate values.
- K-th smallest (max-heap of size K)
- Heap sort
- Median finding (two-heap technique)
Analogy: A hospital ER triage. The sickest patient is always seen first regardless of arrival order. New patients “bubble up” to their correct priority position. When the most urgent is treated, the next most urgent rises to the front.
Key Characteristics
Complete binary tree shape
▶
Stored in a flat array — no pointers, cache-friendly
Heap property: parent ≤/≥ children
▶
Min/max always at root — O(1) peek
Insert: add at end, sift up
▶
O(log n) — at most h swaps up
Extract: swap root with last, sift down
▶
O(log n) — at most h swaps down
Not fully sorted — only parent vs child
▶
Siblings have no ordering — search is O(n)
02
Section Two · Operations
Core Operations
Insert (Offer)
Adds at the end of the array, then sifts up by swapping with parent until heap property is restored.
Pseudocode
function insert(heap, val):
heap.append(val)
i = heap.size - 1 while i > 0:
parent = (i - 1) / 2 if heap[i] < heap[parent]: // min-heap swap(heap, i, parent)
i = parent
else: break // O(log n)
On average, insertions only need O(1) swaps because most values are large and stay near the bottom. Worst case is O(log n) when inserting the new min/max.
Extract Min/Max (Poll)
Removes the root, replaces it with the last element, then sifts down by swapping with the smaller/larger child.
Pseudocode
function extractMin(heap):
min = heap[0]
heap[0] = heap.removeLast()
siftDown(heap, 0)
return min
function siftDown(heap, i):
while 2*i + 1 < heap.size:
smallest = i
left = 2*i + 1
right = 2*i + 2 if heap[left] < heap[smallest]: smallest = left
if right < heap.size and heap[right] < heap[smallest]: smallest = right
if smallest == i: break swap(heap, i, smallest)
i = smallest // O(log n)
Always compare with both children before swapping. In a min-heap, swap with the smaller child. Swapping with the larger child violates the heap property on the other side — the most common bug in manual heap implementations.
Heapify (Build Heap)
Converts an arbitrary array into a valid heap in O(n) by sifting down from the last non-leaf to the root.
Pseudocode
function heapify(arr):
for i = arr.length / 2 - 1 down to 0:
siftDown(arr, i)
// O(n) total — NOT O(n log n)!
Heapify is O(n), not O(n log n). Most nodes are near the bottom and sift very little. The sum converges to O(n). This is why
PriorityQueue(Collection) is faster than inserting one by one.Top-K Pattern
Maintains a min-heap of size K to find the K largest elements in O(n log K).
Pseudocode
function topK(arr, k):
minHeap = new MinHeap()
for val in arr:
minHeap.insert(val)
if minHeap.size() > k:
minHeap.extractMin() // evict smallest return minHeap // O(n log K) time, O(K) space
For K largest, use a min-heap. For K smallest, use a max-heap. The min-heap of size K evicts the smallest, so the K largest survive. The root is the K-th largest.
Common Mistake: Java’s
PriorityQueue is a min-heap by default. For max-heap, pass Comparator.reverseOrder(). In Python, negate values: heappush(h, -val).03
Section Three · Visuals
Diagrams & Array Mapping
Tree vs Array Representation
Same min-heap in tree view and array view with index formulas
Insert (Sift Up) & Extract (Sift Down)
Insert 2: append then bubble up. Extract min: swap root with last then sift down.
Two-Heap Median Pattern
Max-heap (lower half) + min-heap (upper half) → O(1) median access
04
Section Four · Code
Java Quick Reference
Java’s PriorityQueue is a min-heap. For max-heap, pass Comparator.reverseOrder().
Java — PriorityQueue
import java.util.*;
PriorityQueue<Integer> minH = new PriorityQueue<>();
minH.offer(5); minH.offer(1); minH.offer(3);
minH.peek(); // 1 — O(1)
minH.poll(); // 1 — O(log n) PriorityQueue<Integer> maxH = new PriorityQueue<>(Comparator.reverseOrder());
// Top K largest — min-heap of size K PriorityQueue<Integer> topK = new PriorityQueue<>();
for (int n : new int[]{3,1,5,2,4}) {
topK.offer(n);
if (topK.size() > 2) topK.poll();
} // topK = [4, 5]
Heap — Full Implementation
Java — MinHeap from scratch
class MinHeap {
private List<Integer> data = new ArrayList<>();
void offer(int val) { data.add(val); siftUp(data.size()-1); }
int poll() {
int min = data.get(0);
int last = data.remove(data.size()-1);
if (!data.isEmpty()) { data.set(0, last); siftDown(0); }
return min;
}
int peek() { return data.get(0); }
int size() { return data.size(); }
private void siftUp(int i) {
while (i > 0) {
int p = (i-1)/2;
if (data.get(i) >= data.get(p)) break;
Collections.swap(data, i, p); i = p;
}
}
private void siftDown(int i) {
int n = data.size();
while (2*i+1 < n) {
int s = 2*i+1;
if (s+1 < n && data.get(s+1) < data.get(s)) s++;
if (data.get(i) <= data.get(s)) break;
Collections.swap(data, i, s); i = s;
}
}
}
Python — heapq patterns
import heapq
h = []
heapq.heappush(h, 5); heapq.heappush(h, 1); heapq.heappush(h, 3)
h[0] # peek: 1
heapq.heappop(h) # extract: 1 # Max-heap: negate
maxh = []
heapq.heappush(maxh, -5); heapq.heappush(maxh, -1)
-maxh[0] # peek max: 5 # Heapify O(n)
arr = [5,3,8,1,2]
heapq.heapify(arr)
# Top K
heapq.nlargest(2, [3,1,5,2,4]) # [5, 4] def top_k(arr, k):
h = []
for v in arr:
heapq.heappush(h, v)
if len(h) > k: heapq.heappop(h)
return h
JavaScript — MinHeap class
class MinHeap {
constructor() { this.d = []; }
offer(v) { this.d.push(v); this._up(this.d.length-1); }
poll() {
const m = this.d[0], l = this.d.pop();
if (this.d.length) { this.d[0] = l; this._down(0); }
return m;
}
peek() { return this.d[0]; }
get size() { return this.d.length; }
_up(i) {
while (i) {
const p = (i-1)>>1;
if (this.d[i] >= this.d[p]) break;
[this.d[i],this.d[p]] = [this.d[p],this.d[i]]; i = p;
}
}
_down(i) {
const n = this.d.length;
while (2*i+1 < n) {
let s = 2*i+1;
if (s+1<n && this.d[s+1]<this.d[s]) s++;
if (this.d[i] <= this.d[s]) break;
[this.d[i],this.d[s]] = [this.d[s],this.d[i]]; i = s;
}
}
}
C# — PriorityQueue (.NET 6+)
using System.Collections.Generic;
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 5);
pq.Enqueue("high", 1);
pq.Peek(); // "high" (priority 1)
pq.Dequeue(); // "high" // Max-heap: negate priorities var maxPq = new PriorityQueue<int, int>();
maxPq.Enqueue(5, -5);
maxPq.Enqueue(1, -1);
maxPq.Peek(); // 5
05
Section Five · Complexity
Time & Space Complexity
| Operation | Time | Space |
|---|---|---|
| Peek (min/max) | O(1) | O(1) |
| Insert (offer) | O(log n) | O(1) |
| Extract (poll) | O(log n) | O(1) |
| Heapify (build) | O(n) | O(1) in-place |
| Search | O(n) | O(1) |
Why these complexities? Height = log n. Insert sifts up at most log n levels; extract sifts down at most log n. Peek is O(1) — root is always extreme. Heapify is O(n) because most nodes sift very little. Search is O(n): no sibling ordering.
Space Complexity Note
O(n) for n elements in a flat array — no pointers, cache-friendly, more memory-efficient than BSTs. Top-K patterns use only O(K) extra space.
06
Section Six · Decision Guide
When to Use Heap
Use This When
- Repeated min/max access — priority queues, Dijkstra, event schedulers.
- Top-K / K-th element — heap of size K for O(n log K).
- Merge K sorted streams — min-heap picks the next smallest across K sources.
Avoid When
- Need sorted iteration — heaps aren’t sorted; use BST/TreeMap.
- Need O(1) key lookup — no search support; use HashMap.
Comparison
| Structure | Get Min/Max | Insert | Search | Best For |
|---|---|---|---|---|
| Heap ← this | O(1) | O(log n) | O(n) | Priority queue, top-K, Dijkstra |
| BST (balanced) | O(log n) | O(log n) | O(log n) | Sorted data, range queries |
| Sorted Array | O(1) | O(n) | O(log n) | Static data, binary search |
07
Section Seven · Interview Practice
LeetCode Problems
Heap problems: top-K (fixed-size heap), merge K streams (min-heap selects next), stream median (two-heap). If you see “K-th largest/closest” or “merge sorted”, use a heap.
- EasyKth Largest Element in a Stream — Min-heap of size K; peek = K-th largest.
- MediumTop K Frequent Elements — Frequency map + min-heap of size K.
- MediumK Closest Points to Origin — Max-heap of size K by distance.
- MediumMerge K Sorted Lists — Min-heap of K heads; poll smallest, push next. O(N log K).
- HardFind Median from Data Stream — Max-heap (lower) + min-heap (upper), balance sizes.
Interview Pattern: K-th largest = min-heap of size K. K-th smallest = max-heap of size K. Running median = two heaps balanced in size. These three mappings handle 90% of heap problems.