leetcode-23. 合并K个升序链表

class Solution {
public:
    // c++ 定义结构体，重载()，作为函数使用，使用优先队列实现小根堆
    struct Cmp {
        bool operator() (ListNode* a, ListNode* b)
        {
            // 小根堆
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;

        auto dummy = new ListNode(0);
        auto tail = dummy;

        // 把k个链表的头节点放入小根堆中
        for (auto l : lists)
            if (l) heap.push(l);
        
        while (heap.size())
        {
            // 取堆顶最小节点, 并弹出
            auto t = heap.top();
            heap.pop();
            
            tail->next = t;
            tail = t;

            // 堆插入代价是 O(logk)
            if (t->next) heap.push(t->next);
        }

        return dummy->next;
    }
};