← All patternsK-Way Merge · template
Pattern · Heaps
K-Way Merge
Put the first element of each sorted list in a min-heap, repeatedly take the smallest, and push its successor.
Time O(N log k) · Space O(k)
Taught in Module 18: Heaps and Priority Queues
Think of it like this
Merging k sorted queues at a counter: always serve whoever has the smallest ticket number among the people at the front.
Clues that point here
- → Merge k sorted lists or arrays
- → Kth smallest in a sorted matrix
- → Smallest range covering k lists
Not this pattern when
- ✕ Only two lists (simple two-pointer merge)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) if (head != null) heap.offer(head);
ListNode dummy = new ListNode(0), tail = dummy;
while (!heap.isEmpty()) {
ListNode smallest = heap.poll();
tail.next = smallest; tail = smallest;
if (smallest.next != null) heap.offer(smallest.next);
}
return dummy.next;Common versions
- Merge K sorted lists
- Kth smallest element in a sorted matrix
- Find K pairs with smallest sums
Practice problems with this pattern
8.9Merge K Sorted ListsHardmain pattern18.7Kth Smallest Element in a Sorted MatrixMediummain pattern18.8Smallest Range Covering Elements from K ListsHardmain pattern