Merge K Sorted Lists Using Min Heap in DSA Rust

Mental Model

We combine many sorted lists into one sorted list by always picking the smallest current element from all lists using a min heap.

Analogy: Imagine you have several queues of people sorted by height, and you want to form one line sorted by height. You look at the front of each queue and pick the shortest person to join the new line, then move forward in that queue.

List1: 1 -> 4 -> 7 -> null
List2: 2 -> 5 -> 8 -> null
List3: 3 -> 6 -> 9 -> null

MinHeap: [1, 2, 3]
Merged: null

Dry Run Walkthrough

Input: lists: [1->4->7], [2->5->8], [3->6->9]

Goal: Merge all three sorted lists into one sorted list: 1->2->3->4->5->6->7->8->9

Step 1: Insert the first node of each list into the min heap

MinHeap: [1, 2, 3]
Merged: null

Why: We start by knowing the smallest elements from each list to pick the smallest overall

Step 2: Extract min (1) from heap and add to merged list; insert next node (4) from list1 into heap

MinHeap: [2, 3, 4]
Merged: 1 -> null

Why: We add the smallest element to merged and bring in the next candidate from that list

Step 3: Extract min (2) from heap and add to merged list; insert next node (5) from list2 into heap

MinHeap: [3, 4, 5]
Merged: 1 -> 2 -> null

Why: Continue picking smallest and replenishing heap from lists

Step 4: Extract min (3) from heap and add to merged list; insert next node (6) from list3 into heap

MinHeap: [4, 5, 6]
Merged: 1 -> 2 -> 3 -> null

Why: Keep merging by always picking the smallest current node

Step 5: Extract min (4) from heap and add to merged list; insert next node (7) from list1 into heap

MinHeap: [5, 6, 7]
Merged: 1 -> 2 -> 3 -> 4 -> null

Why: Add next smallest and continue until all nodes are merged

Step 6: Extract min (5) from heap and add to merged list; insert next node (8) from list2 into heap

MinHeap: [6, 7, 8]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Keep merging nodes from all lists

Step 7: Extract min (6) from heap and add to merged list; insert next node (9) from list3 into heap

MinHeap: [7, 8, 9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Continue until all nodes are processed

Step 8: Extract min (7) from heap and add to merged list; list1 exhausted, no insertion

MinHeap: [8, 9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Why: One list finished, continue with remaining lists

Step 9: Extract min (8) from heap and add to merged list; list2 exhausted, no insertion

MinHeap: [9]
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

Why: Continue merging remaining nodes

Step 10: Extract min (9) from heap and add to merged list; list3 exhausted, no insertion

MinHeap: []
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Why: All lists exhausted, merging complete

Result:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Annotated Code

DSA Rust

use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct ListNode {
    val: i32,
    next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    fn new(val: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

// Wrapper to reverse ordering for min heap
struct HeapNode(Rc<RefCell<ListNode>>);

impl PartialEq for HeapNode {
    fn eq(&self, other: &Self) -> bool {
        self.0.borrow().val == other.0.borrow().val
    }
}

impl Eq for HeapNode {}

impl PartialOrd for HeapNode {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        // Reverse to make min heap
        Some(other.0.borrow().val.cmp(&self.0.borrow().val))
    }
}

impl Ord for HeapNode {
    fn cmp(&self, other: &Self) -> Ordering {
        // Reverse to make min heap
        other.0.borrow().val.cmp(&self.0.borrow().val)
    }
}

fn merge_k_lists(lists: Vec<Option<Rc<RefCell<ListNode>>>>) -> Option<Rc<RefCell<ListNode>>> {
    let mut heap = BinaryHeap::new();

    // Insert first node of each list into heap
    for list in lists.into_iter() {
        if let Some(node) = list {
            heap.push(HeapNode(node));
        }
    }

    let dummy = ListNode::new(0);
    let mut tail = dummy.clone();

    while let Some(HeapNode(node)) = heap.pop() {
        // Append smallest node to merged list
        tail.borrow_mut().next = Some(node.clone());
        tail = node.clone();

        // If next node exists, push it into heap
        if let Some(next_node) = tail.borrow().next.clone() {
            heap.push(HeapNode(next_node));
        }
    }

    dummy.borrow().next.clone()
}

fn print_list(head: Option<Rc<RefCell<ListNode>>>) {
    let mut curr = head;
    while let Some(node) = curr {
        print!("{} -> ", node.borrow().val);
        curr = node.borrow().next.clone();
    }
    println!("null");
}

fn main() {
    // Create lists: [1->4->7], [2->5->8], [3->6->9]
    let l1 = Some(ListNode::new(1));
    l1.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(4));
    l1.as_ref().unwrap().borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(7));

    let l2 = Some(ListNode::new(2));
    l2.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(5));
    l2.as_ref().unwrap().borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(8));

    let l3 = Some(ListNode::new(3));
    l3.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(6));
    l3.as_ref().unwrap().borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(9));

    let merged = merge_k_lists(vec![l1, l2, l3]);
    print_list(merged);
}

for list in lists.into_iter() { if let Some(node) = list { heap.push(HeapNode(node)); } }

Insert first node of each list into min heap to start merging

while let Some(HeapNode(node)) = heap.pop() {

Extract smallest node from heap to add to merged list

tail.borrow_mut().next = Some(node.clone()); tail = node.clone();

Append extracted node to merged list and move tail pointer

if let Some(next_node) = tail.borrow().next.clone() { heap.push(HeapNode(next_node)); }

If extracted node has next, push it into heap to continue merging

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Complexity Analysis

Time: O(N log k) because we process all N nodes and each heap operation costs O(log k) where k is number of lists

Space: O(k) for the heap storing one node from each list at a time

vs Alternative: Naive merging by repeatedly merging two lists costs O(kN) which is slower than using a min heap

Edge Cases

Empty input lists vector

Returns None immediately, no nodes to merge

DSA Rust

for list in lists.into_iter() { if let Some(node) = list { heap.push(HeapNode(node)); } }

Some lists are empty (None)

Only non-empty lists contribute nodes to heap and merged list

DSA Rust

if let Some(node) = list { heap.push(HeapNode(node)); }

Lists with single element

Heap contains only those single nodes and merges correctly

DSA Rust

while let Some(HeapNode(node)) = heap.pop() { ... }

When to Use This Pattern

When you need to merge multiple sorted lists efficiently, use a min heap to always pick the smallest current element from all lists.

Common Mistakes

Mistake: Not pushing the next node of the extracted node into the heap, causing incomplete merging
Fix: After extracting the smallest node, always push its next node into the heap if it exists

Mistake: Using a max heap or wrong ordering, resulting in incorrect merged order
Fix: Implement custom ordering to make the heap behave as a min heap based on node values

Summary

Merges k sorted linked lists into one sorted list using a min heap.

Use when you have multiple sorted lists and want to merge them efficiently.

Always keep the smallest current nodes in a min heap to pick the next smallest element quickly.

Practice

1. What is the main purpose of using a min heap when merging K sorted lists?

easy

A. To reverse the order of elements in each list

B. To store all elements in sorted order before merging

C. To efficiently get the smallest element among the heads of all lists

D. To split the lists into smaller parts

Solution

1. Step 1: Understand the role of min heap in merging

   A min heap helps quickly find the smallest element among multiple sorted lists by always keeping the smallest element at the top.

2. Step 2: Why is this useful for merging K sorted lists?

   When merging, we repeatedly pick the smallest current element from all lists. The min heap allows this in O(log K) time, making the process efficient.

3. Final Answer:

   To efficiently get the smallest element among the heads of all lists -> Option C

4. Quick Check:

   Min heap = smallest element retrieval [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap stores all elements sorted
• Confusing min heap with max heap
• Using min heap to split lists

2. Which Rust data structure is best suited to implement a min heap for merging K sorted lists?

easy

A. VecDeque

B. LinkedList

C. HashMap

D. BinaryHeap with Reverse wrapper

Solution

1. Step 1: Identify Rust's heap structure

   Rust's standard library provides BinaryHeap which is a max heap by default.

2. Step 2: How to get min heap behavior?

   By wrapping elements with Reverse, BinaryHeap behaves as a min heap, which is perfect for merging sorted lists.

3. Final Answer:

   BinaryHeap with Reverse wrapper -> Option D

4. Quick Check:

   BinaryHeap + Reverse = min heap [OK]

Hint: Use BinaryHeap with Reverse for min heap in Rust [OK]

Common Mistakes:

• Using VecDeque which is a queue, not a heap
• Choosing HashMap which is for key-value pairs
• Using LinkedList which is inefficient here

3. What will be the output of the following Rust code snippet that merges 3 sorted lists using a min heap?

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn merge_k_lists(lists: Vec) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for (i, list) in lists.iter().enumerate() {
        if !list.is_empty() {
            heap.push(Reverse((list[0], i, 0)));
        }
    }
    let mut result = Vec::new();
    while let Some(Reverse((val, list_i, idx))) = heap.pop() {
        result.push(val);
        if idx + 1 < lists[list_i].len() {
            heap.push(Reverse((lists[list_i][idx + 1], list_i, idx + 1)));
        }
    }
    result
}

fn main() {
    let lists = vec![vec![1,4,5], vec![1,3,4], vec![2,6]];
    let merged = merge_k_lists(lists);
    println!("{:?}", merged);
}

medium

A. [1, 1, 2, 3, 4, 4, 5, 6]

B. [1, 2, 3, 4, 5, 6]

C. [6, 5, 4, 4, 3, 2, 1, 1]

D. [1, 1, 3, 4, 4, 5, 6]

Solution

1. Step 1: Initialize heap with first elements

   The heap starts with (1,0,0), (1,1,0), (2,2,0) from the three lists.

2. Step 2: Pop smallest and push next from same list

   Pop 1 from list 0, push 4; pop 1 from list 1, push 3; pop 2 from list 2, push 6; continue until all elements are merged.

3. Final Answer:

   [1, 1, 2, 3, 4, 4, 5, 6] -> Option A

4. Quick Check:

   Merged sorted list = [1,1,2,3,4,4,5,6] [OK]

Hint: Track heap pops and pushes carefully [OK]

Common Mistakes:

• Ignoring duplicates
• Not pushing next element after pop
• Confusing max heap order with min heap

4. Identify the bug in this Rust code snippet for merging K sorted lists using a min heap:

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn merge_k_lists(lists: Vec) -> Vec<i32> {
    let mut heap = BinaryHeap::new();
    for (i, list) in lists.iter().enumerate() {
        heap.push(Reverse((list[0], i, 0)));
    }
    let mut result = Vec::new();
    while let Some(Reverse((val, list_i, idx))) = heap.pop() {
        result.push(val);
        if idx + 1 < lists[list_i].len() {
            heap.push(Reverse((lists[list_i][idx + 1], list_i, idx + 1)));
        }
    }
    result
}

medium

A. The code pushes first element without checking if list is empty

B. The heap should be a max heap, not min heap

C. The loop should use while instead of for

D. The result vector is not initialized

Solution

1. Step 1: Check for empty lists before pushing

   The code pushes list[0] without checking if the list is empty, which can cause a panic.

2. Step 2: Fix by adding a check

   Adding if !list.is_empty() before pushing prevents runtime errors.

3. Final Answer:

   The code pushes first element without checking if list is empty -> Option A

4. Quick Check:

   Empty list check needed before accessing list[0] [OK]

Hint: Always check list is not empty before accessing index 0 [OK]

Common Mistakes:

• Ignoring empty lists causing panic
• Confusing min heap with max heap
• For loop usage is correct here

5. Given K sorted linked lists, how would you modify the min heap merge approach to handle lists with millions of elements efficiently in Rust?

hard

A. Load all elements into memory before merging

B. Use iterators for lazy traversal and push only current nodes into the min heap

C. Use a max heap instead of a min heap for better performance

D. Merge lists pairwise without using any heap

Solution

1. Step 1: Understand memory constraints with large lists

   Loading millions of elements at once can cause memory overflow or slow performance.

2. Step 2: Use iterators for lazy traversal

   Using iterators allows processing one node at a time, pushing only current nodes into the min heap, saving memory and improving efficiency.

3. Step 3: Why other options are less efficient

   Loading all elements wastes memory, max heap is incorrect for smallest element retrieval, and pairwise merging is slower for large K.

4. Final Answer:

   Use iterators for lazy traversal and push only current nodes into the min heap -> Option B

5. Quick Check:

   Lazy iterator + min heap = efficient large list merge [OK]

Hint: Use iterators to avoid loading all elements at once [OK]

Common Mistakes:

• Loading entire lists into memory
• Using max heap instead of min heap
• Ignoring performance impact of pairwise merges