C++中优先队列的用法和普通队列无异,注意比较方式的写法:

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数

在这里我们需要自定义比较,代码如下:

struct comp{  // 自定义比较
    bool operator()(ListNode *a, ListNode *b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode *>, comp> pq;
        for (int i = 0; i < lists.size(); ++i)
            if (lists[i] != NULL) pq.push(lists[i]);
        ListNode dummyHead(0);
        ListNode *p = &dummyHead;
        while(!pq.empty()) {
            ListNode *q = pq.top();
            pq.pop();
            if (q->next) pq.push(q->next);  // 放回
            p = p->next = q;
        }
        return dummyHead.next;
    }
};