Merge K Sorted Lists -- LeetCode 23

[Question]
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

[Analysis]
Merge sort. Maintain a K nodes min-heap. Always purge the smallest element from the heap. 
Building heap of K elements need O(K). Heapifying a new element (from the top) will need O(Log K). Suppose there are total N elements in all lists, the total time will be  O(N Log K).

Below, a array based C++ solution is also provided. The difference will be the data structure used in priority_queue.

[Solution]
// --- C++ ---
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            auto comp=[](ListNode* a, ListNode* b) {
                return a->val < b->val;
            };
            priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);

            for (auto p: lists) if (p) q.push(p);
            ListNode* head = new ListNode(0), *p=head;

            while (!q.empty()) {
                auto node = q.top();
                q.pop();
                p->next = q, p=q;

                if (p->next) q.push(p->next);
            }
            return head->next;
        }
    };

// --- C++, Array based ---
vector<int> sortK (vector<vector<int>>& list) {
    auto comp=[&](pair<int,int> a, pair<int,int> b) {
        return list[a.first][a.second] > list[b.first][b.second];
    };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(comp)> que(comp);

    for (int i=0; i< list.size(); i++)
        if (list[i].size()) que.push({i, 0});

    vector<int> res;
    while (que.size()) {
        auto t = que.top();
        res.push_back(list[t.first][t.second]);

        que.pop();
        if (t.second+1 < list[t.first].size() )
            que.push( {t.first, t.second+1} );

    }
    return res;
}