priority_queue优先队列

红太狼 2022-06-18 08:20 195阅读 0赞

blue学长的STL小课堂之优先队列

/*priority-queue——优先队列*/
    /*
        常用函数:
        q.push(x);//入队
        q.pop();//出队
        q.top();//访问对首元素
        q.empty();//判断是否为空
        q.size();//返回元素数量
    */
    #include <cstdio>
    #include <queue>
    
    using namespace std;
    
    struct info
    {
        int p;
        int q;
        bool operator < (const info &cmp) const
        {
            return p < cmp.p;
        }
        bool operator > (const info &cmp) const
        {
            return p > cmp.p;
        }
    };
    
    int main(int argc, char const *argv[])
    {
        ///创建优先队列
        printf("创建优先队列操作\n");
        ///priority_queue<T> name
        printf("元素类型为int优先队列\n");
        priority_queue<int> q;///创建一个大的先出队的优先队列
        ///priority_queue<int, vector<int>, greater<int> > q;//小的先出队
        printf("\n");
    
        ///入队
        printf("入队操作\n");
        printf("push:1\n");
        q.push(1);//1
        printf("当前对首元素为：%d，队中元素数量：%lu\n", q.top(), q.size());
        printf("push:2\n");
        q.push(2);//2 1
        printf("当前队首元素为：%d，队中元素数量：%lu\n", q.top(), q.size());
        q.push(5);//5 2 1
        printf("当前队首元素为：%d，队中元素数量：%lu\n", q.top(), q.size());
        printf("\n");
    
        ///出队
        printf("出队操作\n");
        printf("pop:%d\n", q.top());
        q.pop();//2 1
        printf("当前对首元素为：%d，队中元素数量：%lu\n", q.top(), q.size());
        printf("push:3\n");
        q.push(3);//3 2 1
        printf("当前对首元素为：%d，队中元素数量：%lu\n", q.top(), q.size());
        printf("pop至队空\n");
        while(!q.empty())
        {
            printf("pop:%d\n", q.top());
            q.pop();
        }
        printf("清空后队中元素数量：%lu\n", q.size());
        printf("\n");
    
        ///创建元素类型为自定义结构体的优先队列
        printf("创建元素类型为自定义结构体的优先队列\n");
        ///priority_queue<info> q2;//需要重载小于号
        priority_queue<info, vector<info>, greater<info> > q2;///需要重载大于号
        q2.push((info){
       1, 5});
        q2.push((info){
       2, 10});
        q2.push((info){
       3, 10});
        while(!q2.empty())
        {
            printf("pop:{%d, %d}\n", q2.top().p, q2.top().q);
            q2.pop();
        }
    
        return 0;
    }

题目练习：

[sdut原题链接][sdut]

数据结构实验之排序四：寻找大富翁  
Time Limit: 200MS Memory Limit: 512KB

Problem Description  
2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。

Input  
首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。

Output  
一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。

Example Input  
6 3  
12 6 56 23 188 60

Example Output  
188 60 56

Hint  
请用堆排序完成。

Author  
xam

以下为memory limit exceeded代码——未根据题意进行优化

#include <cstdio>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    int main(int argc, char const *argv[])
    {
        int n, m, i, v;
        priority_queue<int, vector<int> > q;
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &v);
            q.push(v);
        }
        for(i = 0; i < min(n, m); i++)
        {
            if(i)
                printf(" ");
            printf("%d", q.top());
            q.pop();
        }
        printf("\n");
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Memory Limit Exceeded
    Take time: 0ms
    Take Memory: 512KB
    Submit time: 2017-04-01 17:16:14
    ****************************************************/

以下为time limit exceeded代码——未根据题意进行优化

#include <cstdio>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    int main(int argc, char const *argv[])
    {
        int n, m, i, v;
        priority_queue<int, vector<int> > q;
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &v);
            q.push(v);
        }
        for(i = 0; i < min(n, m); i++)
        {
            if(i)
                printf(" ");
            printf("%d", q.top());
            q.pop();
        }
        printf("\n");
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 210ms
    Take Memory: 0KB
    Submit time: 2017-04-01 17:15:39
    ****************************************************/

以下为accepted代码——priority\_queue

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main(int argc, char *argv[])
    {
        int n, m, i, v, ans[14];
        priority_queue<int, vector<int>, greater<int> > q;
        scanf("%d %d", &n, &m);
        for(i = 0; i < min(n, m); i++)
        {
            scanf("%d", &v);
            q.push(v);
        }
        for(i = min(n, m); i < n; i++)
        {
            scanf("%d", &v);
            q.push(v);
            q.pop();
        }
        for(i = 0; i < min(n, m); i++)
        {
            ans[i] = q.top();
            q.pop();
        }
        for(i = min(n, m)-1; i >= 0; i--)
        {
            printf("%d%c", ans[i], i == 0? '\n': ' ');
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 176ms
    Take Memory: 152KB
    Submit time: 2017-04-01 17:25:02
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3401.html