C++实现优先队列的示例详解

C++实现优先队列的攻略

什么是优先队列？

优先队列是一种特殊的队列，可以根据元素的优先级进行排序和取出元素。即出队时，出队的元素是队列中所有元素中优先级最高的元素。优先队列常常用于任务调度、数据压缩、图像处理等领域。

C++中优先队列的实现

为了方便使用优先队列，C++提供了<queue>库，其内置了优先队列的数据结构，可以直接使用。这个库的底层实现是以堆排序为基础的。使用C++实现优先队列的基本步骤如下：

1. 导入头文件：#include <queue>

2. 定义优先队列：priority_queue<int> pq;

3. 对优先队列进行插入、删除和查询操作。优先队列的常用操作如下：

   • push：插入一个元素。

   • pop：删除队首元素。

   • top：返回队首元素。

   • empty：判断队列是否为空。

   • size：返回队列大小。

4. 在使用优先队列时，需要定义一个元素的优先级，这个通过结构体或类实现。将元素作为结构体或类的成员变量，通过重载比较运算符（<、>）来实现优先级的判断。

C++实现优先队列的示例详解

示例一：求一组数的中位数

在一个包含n个数字的数组中，查找中位数需要对所有数字进行排序或者使用优先队列。

我们可以定义一个小根堆和大根堆，存储比中位数小的数和比中位数大的数，并维护两个堆的大小以保证中位数是第（n+1）/2个数。

代码如下：

#include <queue>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, x;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> larger; // 小根堆
    priority_queue<int, vector<int>, less<int>> smaller; // 大根堆

    for(int i=0; i<n; i++)
    {
        cin >> x;

        // 将x加入到larger或smaller中
        if(larger.size() == 0 || x <= larger.top())
            larger.push(x);
        else
            smaller.push(x);

        // 调整larger和smaller的大小
        if(larger.size() > (n+1)/2)
        {
            int temp = larger.top();
            larger.pop();
            smaller.push(temp);
        }
        else if(smaller.size() > n/2)
        {
            int temp = smaller.top();
            smaller.pop();
            larger.push(temp);
        }

        // 输出当前的中位数
        if((i+1)%2 == 0)
            cout << (smaller.top()+larger.top())/2 << endl;
        else
            cout << larger.top() << endl;
    }
    return 0;
}

示例二：使用自定义的结构体来实现优先队列

我们定义一个结构体 person ，包含姓名和年龄两个成员变量，按照年龄从小到大的顺序来排序。

定义一个比较函数 cmp，使用 less 来定义小于号顺序，使用重载运算符 () 来实现比较。

代码如下：

#include <queue>
#include <iostream>
#include <string>

using namespace std;

struct person {
    string name;
    int age;
};

struct cmp {
    bool operator() (const person &a, const person &b) {
        return a.age > b.age;
    }
};

int main()
{
    priority_queue<person, vector<person>, cmp> pq;

    person p1 = {"Tom", 20};
    person p2 = {"Jerry", 18};
    person p3 = {"John", 23};

    pq.push(p1);
    pq.push(p2);
    pq.push(p3);

    while(!pq.empty()) {
        person p = pq.top();
        pq.pop();
        cout << p.name << " " << p.age << endl;
    }

    return 0;
}

输出：

Jerry 18
Tom 20
John 23