Trộn k mảng đã sắp xếp kích thước khác nhau trong C++

Cho k mảng đã sắp xếp, hãy trộn chúng thành một mảng đã sắp xếp.

Ví dụ: k=3, mảng {2,4}, {3,5,7}, {1,10,11,12} → 1 2 3 4 5 7 10 11 12.

Giải thuật Min-Heap (Priority Queue)

• Đưa phần tử đầu tiên của mỗi mảng vào min-heap, kèm theo chỉ số mảng và chỉ số phần tử.
• Lặp: lấy phần tử nhỏ nhất từ heap, đưa vào kết quả, đẩy phần tử tiếp theo của mảng đó vào heap (nếu còn).
• Độ phức tạp: O(N log k) với N tổng số phần tử.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;
#define ppi pair<int,pair<int,int>>

vector<int> merge(vector<vector<int> > arr){
    vector<int> op;
    priority_queue<ppi, vector<ppi>, greater<ppi> > q;
    for(int i=0;i<arr.size();i++) q.push({arr[i][0],{i,0}});
    while(!q.empty()){
        ppi cur=q.top(); q.pop();
        int i=cur.second.first, j=cur.second.second;
        op.push_back(cur.first);
        if(j+1<arr[i].size()) q.push({arr[i][j+1],{i,j+1}});
    }
    return op;
}

int main(){
    vector<vector<int>> arr{{2,4},{3,5,7},{1,10,11,12}};
    vector<int> output=merge(arr);
    for(int x:output) cout<<x<<" ";
}

Đầu ra

1 2 3 4 5 7 10 11 12