优先队列cmp和sort结果是相反的,return a.price>b.price在sort表示大的在前,在优先队列里,价格低的在前面。
在STL容器和库函数默认使用的是小于号,如果加上greater<>
参数,那么会默认使用大于号,在优先队列中会默认使用小括号表示小于号,并且默认构造一个大根堆,所以把小括号的关系变一下。
—转自y总视频评论
相关例题:
LeetCode 23. 合并K个升序链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
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;
ListNode *phead=new ListNode(-1),*tail=phead;
for(auto x:lists)if(x)heap.push(x);
while(heap.size())
{
auto t=heap.top();
heap.pop();
tail->next=t;
tail=t;
if(t->next)heap.push(t->next);
}
return phead->next;
}
};