Merge K Sorted Lists Using Min Heap in DSA C++ - Time & Space Complexity

Time Complexity: Merge K Sorted Lists Using Min Heap

O(n log k)

Understanding Time Complexity

We want to know how the time to merge multiple sorted lists grows as the number of lists and their sizes increase.

How does using a min heap help us merge efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct ListNode {
    int val;
    ListNode* next;
};

ListNode* mergeKLists(std::vector& lists) {
    auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> minHeap(cmp);
    for (auto list : lists) {
        if (list) minHeap.push(list);
    }
    ListNode dummy; ListNode* tail = &dummy;
    while (!minHeap.empty()) {
        auto node = minHeap.top(); minHeap.pop();
        tail->next = node; tail = tail->next;
        if (node->next) minHeap.push(node->next);
    }
    return dummy.next;
}
    

This code merges k sorted linked lists into one sorted list using a min heap to always pick the smallest current node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Extracting the smallest node from the min heap and inserting the next node from that list.
• How many times: This happens once for each node across all lists, so total n times where n is the total number of nodes.

How Execution Grows With Input

Each of the n nodes is pushed and popped from the min heap, which has size at most k (number of lists).

Input Size (n)	Approx. Operations
10 (k=3)	About 10 insertions and removals from a heap of size 3
100 (k=5)	About 100 insertions and removals from a heap of size 5
1000 (k=10)	About 1000 insertions and removals from a heap of size 10

Pattern observation: The number of operations grows roughly linearly with total nodes n, but each heap operation costs log k time, so total work grows as n times log k.

Final Time Complexity

Time Complexity: O(n log k)

This means the time grows linearly with total nodes n, multiplied by the cost of managing the heap of size k.

Common Mistake

[X] Wrong: "Merging k lists is just like merging two lists, so it takes O(n) time."

[OK] Correct: Merging k lists involves repeatedly choosing the smallest among k current nodes, which requires extra work using a heap, making it slower than just merging two lists.

Interview Connect

Understanding this time complexity helps you explain why using a min heap is efficient for merging multiple sorted lists, a common problem in coding interviews.

Self-Check

"What if we used a simple linear search to find the smallest node instead of a min heap? How would the time complexity change?"