One heap holds at most k items — the current heads. Pop the global smallest, push that list’s next.
“Merge k sorted things” (lists, arrays, streams) → min-heap of heads
Pattern: Heap of Heads
Three lists on stage; the heap of heads never exceeds three entries. Press ▶.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Merge K Sorted Lists
Merge k sorted things (lists, arrays, streams) → min-heap of heads. The heap holds at most k items — the current heads. Pop the global smallest, push that list's next.
Three sorted lists: A=[1,4,5], B=[1,3,4], C=[2,6]. We seed a min-heap with one head from each list. Each step pops the smallest, outputs it, and pushes that list's successor. Watch the heap values change as heads are consumed and replaced.
1
# min-heap holds one head per unfinished list
2
push (head, listId) for every list
3
while heap not empty:
4
v, id = pop() # smallest head
5
output v
6
if list id has next: push(next, id)
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq =
new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists)
if (head != null) pq.offer(head);
ListNode dummy = new ListNode(0), tail = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
tail.next = node;
tail = node;
if (node.next != null) pq.offer(node.next);
}
return dummy.next;
}import heapq
def merge_k_lists(lists):
heap = [(node.val, i, node)
for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
tail.next = tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextstruct Cmp { bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val; } };
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
for (auto h : lists) if (h) pq.push(h);
ListNode dummy, *tail = &dummy;
while (!pq.empty()) {
auto* node = pq.top(); pq.pop();
tail->next = tail = node;
if (node->next) pq.push(node->next);
}
return dummy.next;
}function mergeKLists(lists) {
const heap = new MinHeap((a, b) => a.val - b.val);
for (const head of lists) if (head) heap.push(head);
const dummy = { next: null };
let tail = dummy;
while (heap.size()) {
const node = heap.pop();
tail.next = tail = node;
if (node.next) heap.push(node.next);
}
return dummy.next;
}Python trick: the
(val, i, node)tuple breaks ties by list index sonodeobjects are never compared.
Pairwise merging alternative: merge lists two-at-a-time log k rounds — same O(N log k), no heap needed, great when lists are balanced.
Heap size stays ≤ k forever — that’s where the log k comes from, not from N.
Common Mistakes
- Pushing ALL nodes into the heap: O(N log N), defeats the purpose.
- Comparator sign error in C++ (
>for min-heap,<for max). - Comparing raw node pointers instead of values.
- Losing the tie-break: equal values must still pop deterministically.
Complexity
| Approach | Time | Space |
|---|---|---|
| Concatenate + sort | O(N log N) | O(N) |
| Min-heap of heads | O(N log k) | O(k) |
| Pairwise merge | O(N log k) | O(1) extra |
(N = total elements across all lists)
Premium Content
Unlock Merge K Sorted Structures and all premium lessons with a subscription.
From ₹199.99/year — See plans