Merge K Sorted Arrays ขนาดต่างกันใน C++

โจทย์

กำหนด K sorted arrays ขนาดต่างกัน รวม (merge) เป็น 1 sorted array

ตัวอย่าง: k=3, arrays: {2,4}, {3,5,7}, {1,10,11,12} → 1 2 3 4 5 7 10 11 12

วิธีการแก้ปัญหา

ใช้ Min-Heap (Priority Queue) ขนาด K:

1. Push element แรกของแต่ละ array เข้า heap พร้อมเก็บ (value, array_index, element_index)
2. Pop min จาก heap → เพิ่มในผลลัพธ์
3. Push element ถัดไปจาก array เดียวกันเข้า heap (ถ้ามี)
4. ทำซ้ำจน heap ว่าง

Time: O(N log K) โดย N = total elements

ตัวอย่างโค้ด 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> > queue;
    for (int i = 0; i < arr.size(); i++)
        queue.push({ arr[i][0], { i, 0 } });
    while (queue.empty() == false) {
        ppi current_element = queue.top();
        queue.pop();
        int i = current_element.second.first;
        int j = current_element.second.second;
        op.push_back(current_element.first);
        if (j + 1 < arr[i].size())
            queue.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 i = 0; i < output.size(); i++)
        cout << output[i] << " ";
}

อินพุต

{{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}

เอาต์พุต

1 2 3 4 5 7 10 11 12