Merge K sorted Arrays

Description:

Example:

int[][] A = new int[5][];

A[0] = new int[] { 1, 5, 8, 9 };
A[1] = new int[] { 2, 3, 7, 10 };
A[2] = new int[] { 4, 6, 11, 15 };
A[3] = new int[] { 9, 14, 16, 19 };
A[4] = new int[] { 2, 4, 6, 9 };

Output:
[1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9, 9, 10, 11, 14, 15, 16, 19]

Idea:

http://algorithms.tutorialhorizon.com/merge-k-sorted-arrays/

搞个min heap， 先把每个array的第一个值放进去，然后heap每pop一个值，就从相对的array取下一个值放进去，直到heap为空。

Time: O(nk logk). 因为heap操作一个是logk，一共nk个数据。

Code:

#include <iostream>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

struct HeapNode{
    HeapNode(int v, int i, int j): val(v), ind_arr(i), ind_loc(j) {}
    int val;
    int ind_arr;
    int ind_loc;
};

vector<int> mergeKarray(const vector<vector<int>>& input){
    struct CMP{
        bool operator() (const HeapNode & a, const HeapNode & b) const{
            return a.val > b.val;
        }
    };

    // by default, priority_queue is max_heap
    priority_queue<HeapNode, vector<HeapNode>, CMP> min_heap;

    int k=input.size();

    vector<int> result;

    for(int i=0; i<k; i++){
        if(!input[i].empty()){
            min_heap.push(HeapNode(input[i][0], i, 0));
        }
    }

    while(!min_heap.empty()){
        HeapNode node=min_heap.top();
        min_heap.pop();
        result.push_back(node.val);
        int i=node.ind_arr;
        int j=node.ind_loc;
        if(j+1 < input[i].size()){
            min_heap.push(HeapNode(input[i][j+1], i, j+1));
        }
    }

    return result;
}

int main(){
    vector<vector<int>> sorted_arr;
    sorted_arr.push_back({1, 5, 8, 9});
    sorted_arr.push_back({2, 3, 7, 10});
    sorted_arr.push_back({4, 6, 11, 15});
    sorted_arr.push_back({9, 14, 16, 19});
    sorted_arr.push_back({2, 4, 6, 9});

    vector<int> result;

    result=mergeKarray(sorted_arr);

    for(auto e: result){
        cout<<e<<' ';
    }
    cout<<endl;
}