C++高级数据结构之优先队列

什么是优先队列？

优先队列是一种特殊的队列，其中每个元素都有一个优先级。当加入一个元素时，它会被放置在队列中的适当位置，以确保优先级最高的元素位于队头。从队列中取出元素时，总是从队头删除元素。

优先队列的应用

优先队列的常见应用场景包括：

• 操作系统任务调度
• 网络传输协议TCP中的拥塞控制算法
• 各种图像算法如边缘检测等

C++中STL的优先队列

在C++中，STL中的优先队列是一种堆实现的优先队列，通过实现一个最大堆来保证队头为优先级最高的元素。STL的priority_queue模板类提供了快捷使用的优先队列类，可以在头文件queue中找到。

priority_queue的基本用法

声明一个priority_queue对象的基本语法为：

priority_queue<value_type, container_type, compare_function> pq;

其中：

• value_type：表示存储在优先队列中的元素类型
• container_type：表示用于存储元素的底层容器类型，默认是vector
• compare_function：表示比较元素大小的函数对象，被默认定义为从大到小的比较函数

示例一：从小到大排序

下面是一个简单的例子，演示如何使用priority_queue从小到大排序。我们将使用默认的比较函数，因此只需声明一个priority_queue对象，并将所有元素依次插入即可。

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

int main() {
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}
// Output: 1 1 3 4

示例二：使用自定义比较函数

现在我们来看一个使用自定义比较函数的例子，我们将从大到小排序一个字符串列表，将比较函数定义为按字符串长度比较。

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

bool cmp(const string& a, const string& b) {
    return a.size() < b.size();
}

int main() {
    vector<string> vec = {"hello", "world", "test", "priority", "queue"};
    priority_queue<string, vector<string>, decltype(&cmp)> pq(cmp);
    for (auto& s : vec) {
        pq.push(s);
    }
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}
// Output: priority queue world hello test

总结

优先队列是一种常用的数据结构，C++中的STL提供了方便快捷的使用方式。无论是从小到大排序还是使用自定义比较函数，我们都可以通过STL的priority_queue轻松地实现。