c++优先队列(priority_queue)用法详解

什么是优先队列

优先队列是一种抽象的数据结构，它有点类似与一般的队列，但是又有一些特殊之处。在一个一般的队列中，元素是按照时间顺序排列的。而在优先队列中，元素是按照优先级排列的。也就是说，队头元素是最小或最大的元素。

在C++中，我们可以使用priority_queue来构建优先队列。

优先队列的使用

构建优先队列

在使用优先队列前，需要包含头文件<queue>。构建一个最大值优先的整数优先队列，可以使用如下方式：

#include <queue>
using namespace std;

priority_queue<int> q;

最大值优先的意思是，队头元素为最大值。如果需要构建最小值优先的整数优先队列，则可以按照如下方式构建：

priority_queue<int, vector<int>, greater<int> > q;

元素插入

向优先队列中插入元素时，队列会根据优先级重新排列元素的位置，确保队头元素为最小值或最大值。

q.push(1);
q.push(3);
q.push(2);

在上述代码中，队列中的元素为1，2和3。队头元素为3，因为3是最大值。

元素访问

访问队头元素可以使用top函数。

int top_element = q.top();

在上述代码中，top_element的值将会被赋值为3。

元素弹出

弹出队头元素时，队列会根据优先级重新排列元素的位置，确保队头元素为下一个最小值或最大值。

q.pop();

在上述代码中，队头元素3被弹出。队列中剩余元素为1和2。

总结

在C++中使用优先队列时，需要引入头文件<queue>。使用priority_queue构建优先队列时，需要指定元素类型和优先级比较方式。push函数用于元素插入，top函数用于访问队头元素，pop函数用于弹出队头元素。

示例说明

示例1

以下代码展示了如何使用优先队列计算一组数的中位数。

#include <queue>
#include <iostream>
using namespace std;

int main()
{
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int> > min_pq;
    int n;
    cin >> n;
    while (n--)
    {
        int num;
        cin >> num;
        if (max_pq.size() == 0 || num <= max_pq.top())
            max_pq.push(num);
        else
            min_pq.push(num);
        if (max_pq.size() < min_pq.size())
        {
            int tmp = min_pq.top();
            min_pq.pop();
            max_pq.push(tmp);
        }
        else if (max_pq.size() - min_pq.size() == 2)
        {
            int tmp = max_pq.top();
            max_pq.pop();
            min_pq.push(tmp);
        }
        if (max_pq.size() > min_pq.size())
            cout << max_pq.top() << endl;
        else
            cout << (max_pq.top() + min_pq.top()) / 2 << endl;
    }
    return 0;
}

该程序中定义了一个最大值优先的整数优先队列max_pq和一个最小值优先的整数优先队列min_pq。程序采取了将数据流平均分成两部分的策略，保证优先队列中的元素始终是可以表示数据流上一半的中位数的。

示例2

以下代码展示了如何使用优先队列计算一个无序数组中的第k大元素。

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int> nums{3, 2, 1, 5, 6, 4};
    int k = 2;
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < nums.size(); ++i)
    {
        pq.push(nums[i]);
        if (pq.size() > k)
            pq.pop();
    }
    cout << pq.top() << endl;
    return 0;
}

该程序中定义了一个最小值优先的整数优先队列pq，遍历一次数组后，队列中的元素即为前k大的元素，队头元素即为第k大的元素。

阅读剩余 66%