Heaps
A heap is a specialized tree-based data structure that satisfies the heap property. Heaps are the backbone of priority queues and are essential for efficient sorting and graph algorithms. Think of a heap as a priority-ordered queue: the element with the highest priority (the root) is always instantly accessible, and every node has higher priority than anything below it in the tree — no searching required.
What Is a Heap?#
A heap is a complete binary tree that satisfies the heap property. In a min-heap, every parent node is less than or equal to its children. In a max-heap, every parent node is greater than or equal to its children.
This property guarantees that the minimum (or maximum) element is always at the root — making it retrievable in O(1) time without scanning the entire structure.
Real-World Analogies#
- Hospital emergency room: Patients are treated by severity, not arrival time — the most critical case is always served first
- OS task scheduler: The highest-priority process is always picked next, regardless of when it arrived
- Airline boarding: Priority passengers board before general boarding — ordered by tier, not by check-in time
- Top-K leaderboard: Track the top K scores efficiently without re-sorting the entire list on every update
Types of Heaps#
| Type | Heap Property | Root Value | Common Use |
|---|---|---|---|
| Min-Heap | Parent ≤ Children | Smallest element | Dijkstra's algorithm, event scheduling |
| Max-Heap | Parent ≥ Children | Largest element | HeapSort, priority queues, finding max |
Key Properties#
A valid heap must satisfy two essential properties:
| Property | Description |
|---|---|
| Complete Binary Tree | All levels are fully filled except possibly the last, which is filled left to right |
| Heap Ordering | Every parent node satisfies the heap property with respect to its children |
| Duplicates Allowed | Unlike BSTs, heaps can contain duplicate values |
| Not Sorted | Unlike BSTs, left and right children have no ordering relationship with each other |
| Height | Always O(log n) due to complete binary tree property |
Complete Binary Tree#
The "complete" property is what makes heaps efficient. All levels are fully filled except possibly the last level, which is filled from left to right. Because there are no gaps in the structure, each node's position in memory directly corresponds to its position in the tree — which means we can store the entire heap in a plain array and navigate it with simple index arithmetic, with no pointers needed.
Array Representation#
Heaps are typically stored in arrays, not as linked nodes. This makes them memory-efficient and cache-friendly.
Index Formulas#
For a node at index i (0-based indexing):
| Relationship | Formula | Example (i=1) |
|---|---|---|
| Parent | (i - 1) // 2 | (1-1)//2 = 0 |
| Left Child | 2 * i + 1 | 2*1+1 = 3 |
| Right Child | 2 * i + 2 | 2*1+2 = 4 |
These formulas work because the tree is filled level by level, left to right. Each level holds exactly twice as many nodes as the one above it, so the children of node i always land at positions 2i + 1 and 2i + 2 in the array — a direct consequence of the complete binary tree structure.
Basic Operations#
| Operation | Time Complexity | Description |
|---|---|---|
| peek() | O(1) | Return the root element (min or max) |
| insert() | O(log n) | Add element and restore heap property |
| extractMin/Max() | O(log n) | Remove root and restore heap property |
| heapify() | O(log n) | Restore heap property for a single node |
| buildHeap() | O(n) | Create heap from unsorted array |
heapify() restores order for one node by moving it up or down until it is in the correct position relative to its neighbors. buildHeap() calls heapify() on every non-leaf node to turn an arbitrary array into a valid heap in a single pass.
Insert Operation (Heapify Up)#
To insert an element, we add it at the end of the array — which keeps the tree complete — and then compare it with its parent, swapping upward until the heap property is restored. This upward movement is called heapify up (or bubble up).
We always add at the end rather than searching for the "right" position, because finding that position would take O(n) time. Adding at the end and bubbling up takes only O(log n) — the height of the tree.
Heap Insert (Heapify Up)
Insert element and bubble up to maintain heap property
Extract Min/Max (Heapify Down)#
To remove the root (which is always the min or max), we move the last element in the array to the root position — preserving the complete binary tree shape — then push it downward by repeatedly swapping it with its smaller (for a min-heap) or larger (for a max-heap) child until the heap property is restored. This downward movement is called heapify down (or sift down).
We cannot simply delete the root and shift everything up, as that would break the complete binary tree structure or require O(n) work.
Extract Min (Heapify Down)
Remove root and sift down to maintain heap property
Build Heap#
Building a heap from an unsorted array can be done in O(n) time using bottom-up heapify — significantly faster than inserting elements one by one, which would cost O(n log n).
The key insight is that leaf nodes (roughly the bottom half of the array) are already valid single-element heaps and require no work. We only need to call heapifyDown on the non-leaf nodes, starting from the last one and working up to the root. Because most nodes are near the bottom of the tree and have very few levels to sift through, the total work across all nodes sums to O(n) — not O(n log n).
Build Heap (Heapify)
Convert an unsorted array into a valid heap in O(n) time
Complete Implementation#
Min-Heap Class
Complete min-heap implementation with all operations
HeapSort#
HeapSort sorts an array in-place in O(n log n) time with O(1) extra space — giving it a guaranteed performance advantage over QuickSort, which degrades to O(n²) in the worst case.
The algorithm works in two phases:
- Build a max-heap from the unsorted array — O(n)
- Repeatedly extract the maximum: swap the root (the current maximum) with the last unsorted element, shrink the heap boundary by one, and restore the heap property — repeated n times at O(log n) each
A max-heap is used so that each extraction places the largest remaining element at the end of the array, naturally building up the sorted result from right to left.
HeapSort
Sort array in-place using a max-heap
Common Applications#
Heaps are the right tool whenever you need efficient, repeated access to the minimum or maximum element in a changing dataset.
| Application | How Heap is Used |
|---|---|
| Priority Queue | Efficiently serve highest-priority elements |
| Dijkstra's Algorithm | Select the vertex with minimum distance |
| Prim's MST | Select the edge with minimum weight |
| K-th Largest Element | Use min-heap of size k |
| Merge K Sorted Lists | Track minimum element across lists |
| Median Finder | Use two heaps (max-heap + min-heap) |
| Task Scheduling | Execute highest-priority tasks first |
| Huffman Coding | Build optimal prefix codes |
Heap vs Other Data Structures#
| Operation | Heap | Sorted Array | BST (Balanced) |
|---|---|---|---|
| Find Min/Max | O(1)* | O(1) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete Min/Max | O(log n) | O(1) or O(n)** | O(log n) |
| Search | O(n) | O(log n) | O(log n) |
| Build from array | O(n) | O(n log n) | O(n log n) |
*A min-heap gives O(1) access to the minimum element only; a max-heap gives O(1) access to the maximum element only.
**For a sorted array, removing from the back is O(1), but removing from the front requires shifting all remaining elements — O(n).
When to Use a Heap#
| Scenario | Best Choice | Why |
|---|---|---|
| Need only min or max | Heap | O(1) access, O(log n) operations |
| Need sorted order | BST or Sorted Array | Heap doesn't maintain full sorted order |
| Frequent arbitrary search | BST or Hash Table | Heap search is O(n) |
| K largest/smallest | Heap | Efficient streaming approach |
| Merge sorted streams | Heap | Track minimum across streams |
Reviewing AI-Generated Code#
Heap implementations are prone to subtle bugs around index calculations, comparison direction, and choosing the correct heapify operation. When reviewing AI-generated heap code, focus on these common failure points.
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Index formulas | Parent/child calculations | Off-by-one in 0-based vs 1-based indexing |
| Heapify direction | Bubble up vs sift down | Using wrong direction for operation |
| Min vs Max | Comparison direction | Using < when > needed (or vice versa) |
| Build heap | Starting index | Starting from 0 instead of n//2 - 1 |
| Python heapq | Min-heap only | Forgetting Python heapq is min-heap only |
Spotting AI Heap Bugs
Common errors in AI-generated heap implementations
Summary#
| Concept | Key Takeaway |
|---|---|
| Heap | Complete binary tree with heap ordering property |
| Types | Min-heap (root = min) and Max-heap (root = max) |
| Array Storage | Parent: (i-1)//2, Children: 2i+1, 2i+2 |
| Insert | Add at end, bubble up — O(log n) |
| Extract | Remove root, sift down — O(log n) |
| Build Heap | Bottom-up heapify — O(n) |
| HeapSort | In-place sorting — O(n log n) time, O(1) space |
| Priority Queue | Most common heap application |
The heap is an elegant data structure: simple to implement with a plain array, yet powerful enough to underpin priority queues, in-place sorting, and classical graph algorithms like Dijkstra's and Prim's. Once you internalize the two core operations — heapify up on insert and heapify down on extract — everything else follows naturally.