Merge Sorted Lists - C++ Solution

1. Introduction

This blog post addresses a common problem in data manipulation: merging multiple sorted lists into a single sorted list. This problem is a classic example of utilizing priority queues to efficiently handle sorted sequences.

Problem

Given M sorted lists of variable length, the task is to merge them into a single list that maintains the sorted order.

Example:

Input:

mat = [

[10, 20, 30, 40],

[15, 25, 35],

[27, 29, 37, 48, 93],

[32, 33]

]

Output: [10, 15, 20, 25, 27, 29, 30, 32, 33, 35, 37, 40, 48, 93]

2. Solution Steps

1. Use a min-heap (priority queue in C++) to store the elements along with their corresponding list indices.

2. Initialize the heap with the first element of each list.

3. Extract the smallest element from the heap, and add it to the result list.

4. Insert the next element from the same list into the heap.

5. Repeat steps 3 and 4 until the heap is empty.

3. Code Program

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to merge sorted lists
vector<int> mergeSortedLists(vector<vector<int>>& mat) {
    // Creating a lambda comparator for the min-heap
    auto comp = [](const pair<int, pair<int, int>>& a, const pair<int, pair<int, int>>& b) {
        return a.first > b.first;
    };

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, decltype(comp)> minHeap(comp);
    vector<int> result;

    // Initialize the heap
    for (int i = 0; i < mat.size(); i++) {
        if (!mat[i].empty()) {
            minHeap.push({mat[i][0], {i, 0}});
        }
    }

    // Merge the lists
    while (!minHeap.empty()) {
        auto [val, indices] = minHeap.top();
        minHeap.pop();
        result.push_back(val);

        int listIndex = indices.first;
        int elementIndex = indices.second;
        if (elementIndex + 1 < mat[listIndex].size()) {
            minHeap.push({mat[listIndex][elementIndex + 1], {listIndex, elementIndex + 1}});
        }
    }

    return result;
}

int main() {
    vector<vector<int>> mat = {
        {10, 20, 30, 40},
        {15, 25, 35},
        {27, 29, 37, 48, 93},
        {32, 33}
    };
    vector<int> mergedList = mergeSortedLists(mat);

    for (int num : mergedList) {
        cout << num << " ";
    }
    return 0;
}

Output:

10 15 20 25 27 29 30 32 33 35 37 40 48 93

Explanation:

The mergeSortedLists function uses a min-heap to efficiently merge the sorted lists. Each element in the heap is a pair consisting of the value and its indices in mat. The function initializes the heap with the first element of each list. It then repeatedly extracts the smallest element from the heap, adds it to the result list, and inserts the next element from the same list into the heap. This process continues until the heap is empty, resulting in a merged list that is sorted in ascending order.