Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Created June 10, 2014 23:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zahlenteufel/3eaac2ce492ef19be149 to your computer and use it in GitHub Desktop.
Save zahlenteufel/3eaac2ce492ef19be149 to your computer and use it in GitHub Desktop.
K-Way Merge using C++11
template <typename T>
using minheap = priority_queue<T, vector<T>, greater>;
vector<int> kwaymerge(vector<vector<int>>& vs) {
int k = vs.size();
vector<int> readcount(k, 0);
vector<int> res;
vector<pair<int, int>> vec;
for (int i = 0; i < k; i++) {
if (vs[i].size() > 0){
vec.push_back(make_pair(vs[i].front(), i));
readcount[i]++;
}
}
// this way it uses heapify
minheap q(vec.begin(), vec.end());
while (!q.empty()) {
int v = q.top().first, i = q.top().second; q.pop();
res.push_back(v);
if (readcount[i] < vs[i].size()) {
vec.push_back(make_pair(vs[i][readcount[i], i));
readcount[i]++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment