优先队列 priority_queue

LeetCode上的模板为：

/**
 * 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 Status{
        int val;
        ListNode* ptr;
        bool operator < (const Status &rhs) const{
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for( auto node : lists){
            if(node){
                q.push({node->val, node});
            }
        }
        ListNode head;
        ListNode* tail = &head;
        while( !q.empty() ){
            auto f = q.top();
            q.pop();
            tail->next = f.ptr;
            tail = tail->next;
            if(f.ptr->next){
                q.push({f.ptr->next->val, f.ptr->next});
            }
        }
        return head.next;
    }
};

或者是下面这一种：

//对于暴力的问题要使用自己的思考将其转换成另一个问题，最重要的思想就是分类
//分类就是对结果的所有可能的结果进行分类
//所谓最小的数，就是u里面每个数的对应v里面最小的数的和的最小的数
//其实可以用优先队列的！！！
struct node{
    int u;  //代表下标
    int v;  //代表下标
    int sum;    //代表值

    //注意要自己添上默认的构造函数
    node(){}

    //自己定义的构造函数
    node(int _u,int _v,int _sum):u(_u),v(_v),sum(_sum){}

    friend bool operator <(node a,node b){
        return a.sum > b.sum;
    }
};

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        //堆的大小恒定为nums1.size
        int sizeu = nums1.size();
        int sizev = nums2.size();

        priority_queue<node> q;

        //结果
        int sizer = min(sizeu*sizev,k);
        vector<vector<int>> res(sizer);

        if(sizer == 0){
            return vector<vector<int>>();
        }

        //初始化堆，即建堆
        for(int i=0;i<sizeu;i++){
            q.push(node(i,0,nums1[i]+nums2[0]));
        }

        int sizeh = sizeu;

        int idx = 0;
        while(idx < sizer){
            int u = q.top().u;
            int v = q.top().v;
            res[idx].push_back(nums1[u]);
            res[idx].push_back(nums2[v]);
            
            //如果v到头了
            if(v == sizev-1){
                q.pop();
            }else{
                q.pop();
                q.push(node(u,v+1,nums1[u]+nums2[v+1]));
            }

            idx++;
        }

        return res;
    }
};

使用结构体时，需要自定义优先队列的比较函数，比如输出成绩最好的三个人：

#include <iostream>
#include <queue>

struct student{
	string name;
	int score;
}

struct cmp_custom{
	bool operator()(student& x, student& y){
		return x.score > y.score;
	}
};

void max_k_score()
{
    vector<student> stu_list = {{"Andy", 89}, {"Bella", 79}, {"Cary", 92}, {"Dick", 60}, {"Ray", 70}};
    int k = 3;

    // 小根堆
    priority_queue<student, vector<student>, cmp_custom> q;
}