C++/C++11中std::priority_queue的使用

悠悠 2023-11-07 07:52 103阅读 0赞

一、优先队列的原理及使用

std::priority\_queue:在优先队列中，优先级高的元素先出队列，并非按照先进先出的要求，类似一个堆(heap)。其模板声明带有三个参数，priority\_queue<Type, Container, Functional>, 其中Type为数据类型，Container为保存数据的容器，Functional为元素比较方式。Container必须是用数组实现的容器，比如 vector, deque. STL里面默认用的是vector. 比较方式默认用operator< , 所以如果把后面两个参数缺省的话，优先队列就是大顶堆，队头元素最大。  
二、基本操作

优先队列在头文件\#include <queue>中；

其声明格式为：priority\_queue <int> ans;//声明一个名为ans的整形的优先队列

基本操作有：

empty( ) //判断一个队列是否为空

pop( ) //删除队顶元素

push( ) //加入一个元素

size( ) //返回优先队列中拥有的元素个数

top( ) //返回优先队列的队顶元素

优先队列的时间复杂度为O（logn），n为队列中元素的个数，其存取都需要时间。

三、实例

扔石头

路上有很多石头，当你遇到奇数序列的石头就把他向前仍，偶数的不动，两个石头一起，先考虑扔的距离比较小的石头，这样一直下去，直到前面所有的石头都不可以扔了为止，求最远的石头距离起点多少  
Sample Input

2
    2
    1 5
    2 4
    2
    1 5
    6 6

Sample Output

11
    12

#include<cstdio>
    #include<iostream>
    #include<stack>
    #include<map>
    #include<cstring>
    #include<queue>
    using namespace std ;
    struct stone{//这是一种自定义设置优先队列优先级的方法，重载默认的 < 符号
        int p;
        int d;
        friend bool operator< (stone a,stone b){
            if(a.p==b.p)
                return a.d>b.d;/*注意这里的比较，这是写的数据越小优先级越高，即先取出数值小的元素其实也可以这么理解，队列我们是可以用数组来存储的，比较sort函数里我们写的cmp ，return a>b时 是按降序来排列的，eg ：6 5 4 3 2 1，因为队列又是满足先进先出的原则，所以我们首先取出的是1，也就是数值最小的那个*/
            return a.p>b.p;
        }
    };
    int main()  {
        int t;
        scanf("%d",&t);
        while(t--){
            int n;
            priority_queue<stone> st; 
           scanf("%d",&n);
           stone t;
           for(int i=0;i<n;i++){
            scanf("%d %d",&t.p,&t.d);
            st.push(t);
           }
           int cou=0;
           stone tp;
           while(!st.empty()){
                tp=st.top();
                st.pop();
                if(++cou&1){
                tp.p+=tp.d;
                st.push(tp);
                }
           }
           printf("%d\n",tp.p);
    //代码其它的地方都还是很好理解的.
        }
        return 0 ;
    }

**接水问题**

**学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。**

**现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m，则只有n’个龙头供水，其它m−n’个龙头关闭。**

**现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。**

**输入描述 Input Description  
第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。  
第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同  
学的接水量。**

**输出描述 Output Description  
输出只有一行，1 个整数，表示接水所需的总时间。**

**样例输入 Sample Input  
5 3  
4 4 1 2 1**

**样例输出 Sample Output  
4**

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<vector>
    using namespace std;
    long long num[15002];
    struct cmp{
        bool operator()(long long&a,long long&b)
        {
            return a>b;
        }
     
    };
    bool cmp1(long long A,long long B)
    {
        return A>B;
    }
    int main()
    {
        priority_queue<long long,vector<long long>,cmp>q;
        int m,n;
        int i;long long a;
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            long long maxx=-1211;
            for(i=1;i<=n;i++)
            {
                scanf("%lld",&a);
                q.push(a);
            }long long x;
            if(n>=m)
            {
                while(!q.empty())
                {
                  x=q.top();
                  q.pop();
                  maxx=max(maxx,x);
                }
                printf("%lld\n",maxx);
                continue;
            }
            for(i=0;i<m-n;i++)
            {
                 scanf("%lld",&num[i]);
            }
            for(i=0;i<m-n;i++)
            {
                x=q.top();
                q.pop();
              //  printf("%lld %lld\n",num[i],x);
                q.push(x+num[i]);
            }
            while(!q.empty())
            {
                x=q.top();
                q.pop();
                maxx=max(maxx,x);
            }
            printf("%lld\n",maxx);
        }
        return 0;
    }

合并K个有序链表

Example:

Input:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6

我们首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点即可，代码如下：

class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            auto cmp = [](ListNode*& a, ListNode*& b) {
                return a->val > b->val;
            };
            priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
            for (auto node : lists) {
                if (node) q.push(node);
            }
            ListNode *dummy = new ListNode(-1), *cur = dummy;
            while (!q.empty()) {
                auto t = q.top(); q.pop();
                cur->next = t;
                cur = cur->next;
                if (cur->next) q.push(cur->next);
            }
            return dummy->next;
        }
    };