Heaps & Priority Queues
Data Structures·intermediate·~40 min read
- heap
- priority-queue
- data-structure
A heap is a complete binary tree stored in an array that satisfies the heap property: every parent node is ordered relative to its children. It is the go-to data structure when you need repeated, efficient access to the minimum or maximu…
What you'll learn
The Heap Property
Min-Heap
Every node is less than or equal to its children. The smallest element always lives at the root.
Max-Heap
Every node is greater than or equal to its children. The largest element always lives at the root. ---
Array Representation
A heap is a complete binary tree -- every level is fully filled except possibly the last, which is filled left to right. This makes array storage perfect with zero wasted space.
Why array representation works
Because the tree is complete, there are no gaps. Every index maps to exactly one node in the level-order traversal. This gives us: - No pointer overhead (unlike linked tree structures) - Excellent cache locality (elements are contiguous…
Operations
Insert (Bubble Up / Sift Up) -- O(log n)
To insert, place the new element at the end of the array (maintaining completeness), then "bubble it up" by repeatedly swapping with its parent until the heap property is restored. Why O(log n)? The element can bubble up at most h levels…
Extract Min/Max (Sift Down) -- O(log n)
To extract the root (min or max), swap it with the last element, remove the last element, then "sift down" the new root by swapping with its smallest (for min-heap) child until the heap property is restored. Why O(log n)? The element can…
Peek -- O(1)
Simply return heap[0]. The heap property guarantees the root is always the min (or max). No traversal needed. ---
Build Heap from Array -- O(n)
Given an unsorted array, transform it into a valid heap. The key insight: call sift-down on every non-leaf node, starting from the last non-leaf and working toward the root.
Heapify: The Sift-Down Process
"Heapify" refers to the sift-down operation that restores the heap property for a subtree rooted at index i. It assumes both subtrees are already valid heaps but the root may violate the property. ---
Priority Queue: The Abstract Data Type
A Priority Queue is an ADT that supports: - insert(element, priority) -- add element - extractmin() / extractmax() -- remove and return highest-priority element - peek() -- view highest-priority element without removing A binary heap is…
Python's heapq Module
Python provides a min-heap via the heapq module. There is no built-in max-heap; the standard trick is to negate values.
Custom comparisons with tuples
heapq compares elements lexicographically. Use tuples (priority, data) for custom ordering: If priorities can tie and data is not comparable, add a tiebreaker: ---
Common Patterns
Pattern 1: Top K Elements
To find the K largest elements in a stream or array, maintain a min-heap of size K. The heap root is the Kth largest -- anything smaller gets discarded. Sample Input / Output Input: nums = [5, 2, 9, 1, 7, 4, 8], k = 3 Output: [7, 8, 9] (…
Pattern 2: Kth Largest / Kth Smallest Element
Same as Top K, but you only care about one element: the root of the size-K heap at the end. Why this shape: When a pattern section presents multiple approaches, each complexity claim now includes a one-line derivation showing how the for…
Pattern 3: Merge K Sorted Lists
Sample Input / Output Input: lists = [[1,4,7], [2,5,8], [3,6,9]] Output: [1,2,3,4,5,6,7,8,9] Input: lists = [[1], [2], [3]] Output: [1,2,3] — edge case: each list has one element Input: lists = [[1,2,3], [], [4,5]] Output: [1,2,3,4,5] —…
Pattern 4: Running Median
Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. The median is at one of the roots. Sample Input / Output Input: Stream of numbers [5, 2, 8] Output: After 5: 5, After 2: 3.5, After 8: 5 Input: Stream o…
Pattern 5: Task Scheduling / Meeting Rooms
Use a min-heap to track the earliest available time (or end time of current meetings). Meeting Rooms II: Find minimum number of conference rooms needed. Sample Input / Output Input: intervals = [(0, 30), (5, 10), (15, 20)] Output: 2 (nee…
Complexity Summary
| Operation | Time | Space | |-----------|------|-------| | Insert (push) | O(log n) | O(1) | | Extract min/max (pop) | O(log n) | O(1) | | Peek | O(1) | O(1) | | Build heap | O(n) | O(1) in-place | | Search for arbitrary element | O(n)…
When to Use Heaps
Use a heap when: - You need repeated access to the min or max element - You are processing a stream and need to maintain order of top/bottom K - You need to merge multiple sorted sequences efficiently - Task/job scheduling based on prior…
Pattern 6: Sort a K-Sorted (Nearly Sorted) Array
Problem: Given an array where each element is at most K positions from its sorted position, sort it efficiently. Sample Input / Output Input: arr = [6, 5, 3, 2, 8, 10, 9], K = 3 Output: [2, 3, 5, 6, 8, 9, 10] Input: arr = [2, 1, 3, 4], K…
Pattern 7: Connect Ropes to Minimize Cost
Problem: Given N ropes of different lengths, connect them into one rope. The cost of connecting two ropes is the sum of their lengths. Find the minimum total cost. Sample Input / Output Input: ropes = [4, 3, 2, 6] Output: 29 (2+3=5, then…
Common Mistakes
1. Forgetting Python's heapq is min-heap only -- negate values for max-heap behavior 2. Using heapq on non-comparable objects -- wrap in tuples with a tiebreaker counter 3. Confusing heap sort with build-heap complexity -- build is O(n),…
Practice Problems Walkthrough
Problem: Kth Largest Element in an Array
Find the Kth largest element in an unsorted array (e.g., 3rd largest). Sample Input / Output Input: nums = [3, 2, 1, 5, 6, 4], k = 2 Output: 5 (the 2nd largest element) Input: nums = [3, 2, 1, 5, 6, 4], k = 6 Output: 1 — edge case: k=n r…
Problem: Find Median from Data Stream
Design a data structure that supports adding numbers and finding the median in O(log n) and O(1) time respectively. Sample Input / Output Operations: addNum(5), addNum(2), findMedian(), addNum(8), findMedian() Output: 3.5 (median after […
Practice Checklist
| Pattern | Key Insight | Complexity | |---------|-------------|-----------| | Top K largest | Min-heap of size K, evict root if new > root | O(n log k) | | Kth largest | Same as top K, answer is root | O(n log k) | | Merge K sorted | He…