A complete binary tree satisfying the heap property — min-heap or max-heap — enabling O(1) access to the minimum or maximum and O(log n) insert and extract. The backbone of priority queues, Dijkstra's algorithm, and heap sort.
Trees
Heap Fundamentals
A complete binary tree with one structural guarantee — the heap property: in a min-heap every parent is less than or equal to its children, in a max-heap every parent is greater than or equal. This invariant keeps the extreme value at the root for O(1) access, while the complete-tree shape enables O(1) array storage with no pointers — making heaps the engine behind priority queues, Dijkstra's algorithm, and heap sort.
A heap is a complete binary tree satisfying the heap property — in a min-heap, every parent node's value is less than or equal to its children's values; in a max-heap, every parent is greater than or equal to its children. The complete-tree property means all levels are fully filled except possibly the last, which fills left-to-right — and this structural guarantee enables a remarkably efficient trick: the entire tree can be stored in a flat array with no pointers. The root sits at index 1, the left child of node i at 2i, the right child at 2i+1, and the parent at ⌊i/2⌋ — pure index arithmetic replaces every pointer dereference. The heap property guarantees that the minimum (or maximum) is always at the root, giving O(1) access to the extreme value. Insert and extract operations maintain both invariants in O(log n) time by bubbling up (swap with parent until the heap property holds) or bubbling down (swap with the smaller child until the heap property holds). Java's PriorityQueue is a binary min-heap under the hood. Heaps power Dijkstra's shortest-path algorithm, heap sort, and any problem requiring repeated extraction of the minimum or maximum from a dynamic collection. Understanding heaps means understanding how array index arithmetic replaces pointer navigation entirely.
Analogy: A hospital emergency triage queue — patients are always treated in order of severity (priority), not arrival time. Adding a new patient inserts them at the right severity level (bubble up), and treating a patient removes the most critical one and reorganises the queue (bubble down). The head of the queue is always the most urgent case — that is your heap root. You never scan every patient to find the most critical; the triage system guarantees the most urgent is always at the front. A heap provides the exact same guarantee for data.
02
Section Two · Mental Model
How It Thinks
Complete binary tree property
▶
Enables array storage with O(1) index arithmetic — no pointers, no wasted space, cache-friendly sequential memory layout
Heap property: parent ≤ children (min-heap)
▶
Minimum is always at the root — O(1) peek at the global minimum without any search or traversal
Insert: add at end, bubble up
▶
Maintains complete tree shape first, then restores heap property by swapping upward — O(log h) = O(log n)
Extract-min: remove root, move last to root, bubble down
Because the tree is always complete — no degenerate case exists, performance is guaranteed unlike an unbalanced BST
Build heap from array in O(n)
▶
Heapify from bottom-up is more efficient than n individual inserts — the Floyd algorithm insight that most nodes are near the leaves
03
Section Three · Heap Properties
The Two Invariants — Shape and Order
Heaps have two invariants that must hold simultaneously — the shape invariant (complete binary tree) and the order invariant (heap property). Understanding these separately is the key to understanding every heap operation: insert restores shape first then order, extract-min restores order after replacing the root with the last element. Every bug in a heap implementation traces back to violating one of these two invariants.
Heap anatomy — tree, array mapping, and index arithmetic
Heap Properties Reference
Property
Definition
Example
Heap property (min)
parent.val ≤ children.val for all nodes
3 ≤ 7 and 3 ≤ 9
Heap property (max)
parent.val ≥ children.val for all nodes
9 ≥ 7 and 9 ≥ 3
Complete tree
All levels full except last; last fills left-to-right
Nodes at indices 1..n
Array mapping
Node i: left=2i, right=2i+1, parent=⌊i/2⌋
Node 3: left=6, right=7
Root is extremum
Min-heap root = global minimum; max-heap root = global maximum
heap[1] is always min
Height
Always ⌊log₂ n⌋ — guaranteed O(log n)
7 nodes → height=2
Size
n nodes occupy indices 1..n; index 0 unused
Array size = n+1
Why index 0 is unused:
Using 1-based indexing makes the parent/child arithmetic clean — parent = i/2 with integer division, left = 2i, right = 2i+1.
If 0-based indexing is used instead, the formulas become left = 2i+1, right = 2i+2, parent = (i−1)/2 — correct but slightly messier.
Java's PriorityQueue uses 0-based indexing internally; most textbook heaps use 1-based for clarity.
04
Section Four · Heap Types
Min-Heap, Max-Heap, and the Two-Heap Pattern
Three heap variants appear in interviews and systems — min-heap, max-heap, and the two-heap pattern. Java's PriorityQueue is a min-heap by default; a max-heap requires a reversed comparator. The two-heap pattern (one min-heap + one max-heap) is the algorithmic key to median-finding problems and appears in several hard interview questions.
Min-Heap vs Max-Heap vs Two-Heap Pattern
Heap Type Comparison
Type
Root holds
Java creation
Use case
Min-Heap
Global minimum
new PriorityQueue<>()
Dijkstra, K smallest, scheduling
Max-Heap
Global maximum
new PriorityQueue<>(Comparator.reverseOrder())
K largest, sliding window max
Two-Heap
—
One of each
Running median, data stream
D-ary Heap
Min or Max
Custom
Decrease-key heavy workloads
K largest → use a min-heap of size K:
Counterintuitive but correct — maintaining a min-heap of the K largest elements seen so far lets you evict the smallest of the K whenever a new element arrives.
The heap top is always the Kth largest element.
For K smallest, the mirror applies: use a max-heap of size K and evict the largest when a new smaller element arrives.
05
Section Five · Core Operations
Insert, Extract, Peek, and Decrease-Key
Insert (Bubble Up)
Add element at the next available position (end of array), then swap with parent while the heap property is violated — O(log n).
Pseudocode
functioninsert(heap, val):
append val to end of heap // maintain complete tree shape
i = last index
while i > 1 and heap[i] < heap[parent(i)]:
swap(heap[i], heap[parent(i)])
i = parent(i) // bubble up// O(log n) — at most h swaps
Insert — adding value 2 into min-heap [1, 3, 5, 7, 9]
Bubble-up only travels one root-to-leaf path:
— at most log₂n swaps. The complete tree property guarantees this path is short.
No matter how large the heap, insert never visits more nodes than the height of the tree.
Extract-Min (Bubble Down)
Remove and return the root (minimum), replace it with the last element, then swap with the smaller child while the heap property is violated — O(log n).
Pseudocode
functionextractMin(heap):
min = heap[1] // save root
heap[1] = heap[last] // move last to root
remove last element // shrink heap
i = 1
while true:
smallest = i
if left(i) exists and heap[left(i)] < heap[smallest]: smallest = left(i)
if right(i) exists and heap[right(i)] < heap[smallest]: smallest = right(i)
if smallest == i: break// heap property restoredswap(heap[i], heap[smallest])
i = smallest // bubble down// O(log n)
Extract-min from heap [1, 3, 5, 7, 9, 8]
Always swap with the SMALLER child in a min-heap:
— otherwise you promote a value larger than the other child, creating a new violation.
In a max-heap, swap with the LARGER child. This is the most common implementation bug in heap operations.
Peek
Return the root without removing it — O(1).
Pseudocode
functionpeek(heap):
if heap is empty: throw exception
return heap[1] // root is always the minimum// O(1)
Peek is O(1) because the heap property guarantees the minimum is always at the root.:
No traversal needed.
This is the entire reason to use a heap over a sorted array when you only need repeated min/max access — the sorted array gives O(1) min but O(n) insert, while the heap gives O(1) peek and O(log n) insert.
Decrease-Key / Update Priority
Update a node's value to a smaller value (min-heap), then bubble up to restore heap property — O(log n). Used in Dijkstra's algorithm.
Pseudocode
functiondecreaseKey(heap, i, newVal):
if newVal > heap[i]: throw error // can only decrease
heap[i] = newVal
while i > 1 and heap[i] < heap[parent(i)]:
swap(heap[i], heap[parent(i)])
i = parent(i) // same as bubble-up// O(log n)
Java's PriorityQueue does NOT support decrease-key efficiently:
— there's no O(log n) update.
The workaround is lazy deletion: add the updated node as a new entry and mark the old entry as stale, ignoring stale entries on extraction.
This is the standard approach in Dijkstra implementations with Java's PriorityQueue.
Operations Summary
Operation
Time
Space
Notes
peek (min/max)
O(1)
O(1)
Root is always the extremum
insert
O(log n)
O(1)
Bubble up at most h levels
extract-min/max
O(log n)
O(1)
Bubble down at most h levels
build heap
O(n)
O(1)
Floyd's heapify — not n inserts
decrease-key
O(log n)
O(1)
Not supported directly in Java
search
O(n)
O(1)
No ordering beyond parent>children
Common Mistake: Calling PriorityQueue.remove(element) to update priorities — this is O(n) because it searches linearly. For Dijkstra with frequent updates, use the lazy deletion pattern (re-add with new priority, skip stale extractions) to stay O((V+E) log V).
06
Section Six · Heapify
Heapify — Building a Heap in O(n)
The naïve approach to building a heap is n individual inserts — O(n log n). Floyd's heapify algorithm builds a valid heap from an unsorted array in O(n) by starting from the last internal node (index n/2) and calling sift-down toward index 1. Leaves are already valid 1-node heaps; sift-down on higher nodes is cheap because subtrees below are already heapified. The O(n) proof is non-obvious but important: most nodes are near the leaves where sift-down costs O(1).
Sift-Down — O(log n)
functionsiftDown(heap, i, size):
while true:
smallest = i
l = 2*i; r = 2*i+1
if l <= size and heap[l] < heap[smallest]: smallest = l
if r <= size and heap[r] < heap[smallest]: smallest = r
if smallest == i: breakswap(heap[i], heap[smallest])
i = smallest
Build Heap — O(n)
functionbuildHeap(array):
n = array.length
// start from last internal node, go to rootfor i from n/2 down to 1:
siftDown(array, i, n)
// array is now a valid min-heap
n individual inserts, each O(log n). Simple but suboptimal. Acceptable when building from a stream of incoming elements where you must maintain heap order after every arrival.
O(n) — Floyd's Heapify
Start from last internal node, sift-down to root. Each sift-down costs O(height of subtree). The sum of subtree heights = O(n) by a geometric series argument. Use when building from a known array.
The O(n) complexity proof:
Sum the heights of all nodes — there are n/2 leaves (height 0), n/4 nodes at height 1, n/8 at height 2, and so on.
The total work is n/2·0 + n/4·1 + n/8·2 + ... which converges to O(n) by a geometric series.
This is why heapify beats n individual inserts — most of the work happens at the leaves where the cost is zero.
07
Section Seven · Heap Sort
Heap Sort — O(n log n) In-Place
Heap sort combines build-heap (O(n)) with n extract-max operations (O(log n) each) to produce a sorted array in O(n log n) time with O(1) extra space. Unlike merge sort, it requires no extra array. Unlike quicksort, it has guaranteed O(n log n) worst-case. The key insight: after extract-max, place the maximum at the array's end — the sorted portion grows from right to left while the heap shrinks from right to left.
Pseudocode
functionheapSort(array):
// Phase 1: Build max-heap in-place — O(n)buildMaxHeap(array)
// Phase 2: Extract max n-1 times — O(n log n)for i from n down to 2:
swap(array[1], array[i]) // move max to sorted positionsiftDown(array, 1, i-1) // restore heap on shrunk array// array is now sorted ascending
Heap sort on [3, 1, 4, 1, 5]
Sorting Algorithm Comparison
Algorithm
Time (best)
Time (avg)
Time (worst)
Space
Stable
Heap Sort
O(n log n)
O(n log n)
O(n log n)
O(1)
No
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Yes
Quick Sort
O(n log n)
O(n log n)
O(n²)
O(log n)
No
Why heap sort loses in practice:
Heap sort is rarely used despite its theoretical advantages.
Its non-sequential memory access pattern (jumping between parent and child indices in the array) causes poor cache performance.
QuickSort, with its sequential access patterns, typically outperforms heap sort by 2–5× on real hardware despite the worst-case risk.
Java's Arrays.sort() uses a dual-pivot quicksort for primitives and TimSort (merge sort variant) for objects.
08
Section Eight · Implementation
Build It Once
Build this from scratch once — the array index arithmetic becomes mechanical after one implementation. In interviews, Java's PriorityQueue is the tool; understanding the internals makes you dangerous with it.
Java — MinHeap core mechanics
// Min-heap backed by an int array — 1-based indexing// Root at index 1; left child of i = 2i; right = 2i+1; parent = i/2public classMinHeap {
privateint[] heap;
privateint size;
publicMinHeap(int capacity) {
heap = newint[capacity + 1]; // index 0 unused
size = 0;
}
// INSERT — O(log n)public voidinsert(int val) {
heap[++size] = val;
bubbleUp(size);
}
// EXTRACT-MIN — O(log n)publicintextractMin() {
if (size == 0) throw newNoSuchElementException();
int min = heap[1];
heap[1] = heap[size--];
bubbleDown(1);
return min;
}
// PEEK — O(1)publicintpeek() { return heap[1]; }
}
import java.util.*;
public classMinHeap {
privateint[] heap;
privateint size;
publicMinHeap(int capacity) {
heap = newint[capacity + 1]; // 1-based indexing
size = 0;
}
// ── Insert ─────────────────────────────────────── O(log n)public voidinsert(int val) {
heap[++size] = val;
bubbleUp(size);
}
// ── Extract Min ────────────────────────────────── O(log n)publicintextractMin() {
if (size == 0) throw newNoSuchElementException();
int min = heap[1];
heap[1] = heap[size--];
bubbleDown(1);
return min;
}
// ── Peek ───────────────────────────────────────── O(1)publicintpeek() {
if (size == 0) throw newNoSuchElementException();
return heap[1];
}
publicintsize() { return size; }
publicbooleanisEmpty() { return size == 0; }
// ── Bubble Up ──────────────────────────────────── O(log n)private voidbubbleUp(int i) {
while (i > 1 && heap[i] < heap[i / 2]) {
swap(i, i / 2);
i /= 2;
}
}
// ── Bubble Down ────────────────────────────────── O(log n)private voidbubbleDown(int i) {
while (2 * i <= size) { // has at least left childint smallest = 2 * i; // left childif (smallest < size && heap[smallest + 1] < heap[smallest])
smallest++; // right child is smallerif (heap[i] <= heap[smallest]) break;
swap(i, smallest);
i = smallest;
}
}
private voidswap(int a, int b) {
int t = heap[a]; heap[a] = heap[b]; heap[b] = t;
}
// ── Build Heap (Floyd's Heapify) ──────────────── O(n)public staticMinHeapbuildHeap(int[] arr) {
MinHeap h = newMinHeap(arr.length);
h.size = arr.length;
System.arraycopy(arr, 0, h.heap, 1, arr.length);
for (int i = h.size / 2; i >= 1; i--)
h.bubbleDown(i);
return h;
}
// ── Heap Sort (in-place, ascending) ───────────── O(n log n)public static voidheapSort(int[] arr) {
int n = arr.length;
// Build max-heap (use >= instead of <= in sift)for (int i = n / 2 - 1; i >= 0; i--)
siftDownMax(arr, i, n);
// Extract max repeatedlyfor (int i = n - 1; i > 0; i--) {
int t = arr[0]; arr[0] = arr[i]; arr[i] = t;
siftDownMax(arr, 0, i);
}
}
private static voidsiftDownMax(int[] a, int i, int n) {
while (2 * i + 1 < n) {
int largest = 2 * i + 1;
if (largest + 1 < n && a[largest + 1] > a[largest]) largest++;
if (a[i] >= a[largest]) break;
int t = a[i]; a[i] = a[largest]; a[largest] = t;
i = largest;
}
}
// ─── PriorityQueue Usage Patterns ─────────────────────────// Top K Largest — min-heap of size k O(n log k)public staticList<Integer> topKLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = newPriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) minHeap.poll(); // evict smallest
}
return newArrayList<>(minHeap);
}
// Kth Smallest — max-heap of size k O(n log k)public staticintkthSmallest(int[] nums, int k) {
PriorityQueue<Integer> maxHeap =
newPriorityQueue<>(Comparator.reverseOrder());
for (int num : nums) {
maxHeap.offer(num);
if (maxHeap.size() > k) maxHeap.poll(); // evict largest
}
return maxHeap.peek(); // top = kth smallest
}
// ── Main ─────────────────────────────────────────────public static voidmain(String[] args) {
// 1. Build heap from arrayMinHeap h = MinHeap.buildHeap(newint[]{9, 4, 7, 2, 8, 1, 5});
System.out.println("Min: " + h.peek()); // → 1// 2. Extract all in sorted orderwhile (!h.isEmpty())
System.out.print(h.extractMin() + " ");
// → 1 2 4 5 7 8 9System.out.println();
// 3. Top 3 largestSystem.out.println("Top 3: " +
topKLargest(newint[]{3,1,4,1,5,9,2,6}, 3));
// → [5, 9, 6]// 4. Heap sortint[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
heapSort(arr);
System.out.println("Sorted: " + Arrays.toString(arr));
// → [1, 1, 2, 3, 4, 5, 6, 9]
}
}
Python — Heap implementation + heapq patterns
import heapq
# ── MinHeap class (manual implementation) ────────────classMinHeap:
def__init__(self):
self.heap = [0] # index 0 unused (1-based)
self.size = 0
definsert(self, val):
self.heap.append(val)
self.size += 1
self._bubble_up(self.size)
defextract_min(self):
if self.size == 0:
raiseIndexError("empty heap")
min_val = self.heap[1]
self.heap[1] = self.heap[self.size]
self.heap.pop()
self.size -= 1
if self.size > 0:
self._bubble_down(1)
return min_val
defpeek(self):
return self.heap[1]
def_bubble_up(self, i):
while i > 1 and self.heap[i] < self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i //= 2
def_bubble_down(self, i):
while 2 * i <= self.size:
smallest = 2 * i
if smallest < self.size and self.heap[smallest + 1] < self.heap[smallest]:
smallest += 1
if self.heap[i] <= self.heap[smallest]:
break
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
# ── Using Python's heapq module (min-heap) ───────────
h = []
heapq.heappush(h, 5) # insert
heapq.heappush(h, 3)
heapq.heappush(h, 7)
min_val = heapq.heappop(h) # extract min → 3
peek = h[0] # peek min (no pop) → 5# Build heap from list — O(n)
arr = [9, 4, 7, 2, 8, 1, 5]
heapq.heapify(arr) # arr is now a valid min-heap in-place# ── Max-heap simulation using negation ────────────────
max_heap = []
for val in [3, 1, 4, 1, 5]:
heapq.heappush(max_heap, -val) # negate on push
max_val = -heapq.heappop(max_heap) # negate on pop → 5# ── Top K Largest — min-heap of size K ────────────────deftop_k_largest(nums, k):
return heapq.nlargest(k, nums) # built-in!# ── Kth Smallest ──────────────────────────────────────defkth_smallest(nums, k):
return heapq.nsmallest(k, nums)[-1]
# ── Heap Sort ─────────────────────────────────────────defheap_sort(arr):
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]
Common Mistake: Never call new PriorityQueue<>(array) and expect it to work — PriorityQueue has a constructor that takes a Collection, so new PriorityQueue<>(Arrays.asList(array)) builds a heap from the list in O(n). But if you pass an int[] directly, Java sees it as a capacity hint, not initial elements.
09
Section Nine · Java Reference
Use It In Java
IN JAVA — PriorityQueue<E>
PriorityQueue<E> — binary min-heap by default
PriorityQueue<E> in java.util — binary min-heap by default. For max-heap, pass Comparator.reverseOrder(). Implements the Queue interface. Unbounded (grows automatically).
// MIN-HEAP (default)PriorityQueue<Integer> minHeap = newPriorityQueue<>();
minHeap.offer(5); // insert — O(log n)
minHeap.offer(3);
minHeap.offer(7);
minHeap.peek(); // view min — O(1), returns null if empty
minHeap.poll(); // remove min — O(log n), returns null if empty
minHeap.size(); // O(1)
minHeap.isEmpty(); // O(1)// MAX-HEAPPriorityQueue<Integer> maxHeap =
newPriorityQueue<>(Comparator.reverseOrder());
// CUSTOM OBJECTS — sort by fieldPriorityQueue<int[]> pq =
newPriorityQueue<>((a, b) -> a[0] - b[0]); // by first element// BUILD FROM COLLECTION — O(n)PriorityQueue<Integer> fromList =
newPriorityQueue<>(Arrays.asList(3, 1, 4, 1, 5));
PriorityQueue Methods
Method
Time
Notes
offer(e) / add(e)
O(log n)
add throws on capacity limit (unbounded: same)
peek()
O(1)
Returns null if empty; use for min-heap top
poll()
O(log n)
Returns null if empty
remove(Object o)
O(n)
Linear scan — avoid for priority updates
contains(Object o)
O(n)
Linear scan — heap has no search structure
size()
O(1)
toArray()
O(n)
Array is NOT sorted — heap order only
⚠ Gotcha:PriorityQueue.toArray() and iterating a PriorityQueue with a for-each loop do NOT return elements in sorted order — they return elements in internal heap order. To get sorted output, repeatedly poll() until empty. This is a common interview mistake.
When to use PriorityQueue
Use PriorityQueue for any problem requiring repeated access to the minimum or maximum element: K largest/smallest, merge K sorted lists, Dijkstra's shortest path, task scheduling by priority, sliding window maximum. For static sorted data, use Arrays.sort() or Collections.sort() instead — a heap is only advantageous when elements arrive or are removed dynamically.
⚠ Gotcha: The comparator subtraction pattern (a, b) -> a - b overflows when a and b have opposite signs and large magnitudes. Use Integer.compare(a, b) or Comparator.comparingInt(x -> x[0]) for safety in production code and interviews.
10
Section Ten · Practice
Problems To Solve
Heap problems in interviews break into three patterns: K-element problems (use a heap of size K to find K largest/smallest in a stream), merge problems (use a min-heap to merge K sorted arrays or lists by always extracting the global minimum), and graph problems (Dijkstra's algorithm uses a min-heap to always process the nearest unvisited node). Recognise which pattern applies from the problem statement — "K largest", "K smallest", "K closest", "merge K sorted" — and the heap structure follows immediately.
Simulate by repeatedly extracting the two largest stones from a max-heap and inserting the remainder if nonzero. Terminate when one or zero stones remain.
Two-heap pattern: max-heap for lower half, min-heap for upper half; rebalance after each insert so sizes differ by at most 1. Median is the top of the larger heap (or average of both tops).
Min-heap storing (value, list-index, node-index); always extract the global minimum across all lists and advance that list's pointer. O(N log K) where N is total elements.
