优先队列 priority

LeetCode上的模板为：

class Solution {
public:
    struct Status{
        int val;
        ListNode* ptr;
        bool operator < (const Status &rhs) const{
            return val > rhs.val;
        }
    };

    priority_queue  q;

    ListNode* mergeKLists(vector& 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> kSmallestPairs(vector& nums1, vector& nums2, int k) {
        //堆的大小恒定为nums1.size
        int sizeu = nums1.size();
        int sizev = nums2.size();

        priority_queue q;

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

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

        //初始化堆，即建堆
        for(int i=0;i 
使用结构体时，需要自定义优先队列的比较函数，比如输出成绩最好的三个人：
 
#include 
#include 

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 stu_list = {{"Andy", 89}, {"Bella", 79}, {"Cary", 92}, {"Dick", 60}, {"Ray", 70}};
    int k = 3;

    // 小根堆
    priority_queue, cmp_custom> q;
}

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5699315.html