STL中的`priority_queue`是一种特殊的容器适配器，它模拟了一个优先队列的数据结构。优先队列的主要特性是每次从队列头部取出的是具有最高优先级的元素，即最大值（默认情况下）。这个数据结构在很多算法和问题中都有应用，如事件驱动模拟、任务调度等。
**构造与析构**
1. `priority_queue()` - 默认构造函数，创建一个空的优先队列。
2. `priority_queue(const priority_queue&)` - 拷贝构造函数，复制一个已存在的优先队列。
3. `priority_queue(const Compare& comp)` - 使用指定的比较函数`comp`创建一个空的优先队列。
4. `priority_queue(const value_type* first, const value_type* last)` - 使用指定范围的元素创建优先队列，使用默认的比较函数。
5. `priority_queue& operator=(const priority_queue &)` - 赋值运算符，将一个优先队列的元素复制到另一个优先队列。
6. `~priority_queue()` - 析构函数，销毁所有元素并释放内存。
**常用函数**
1. `empty()` - 判断优先队列是否为空，返回布尔值。
2. `push(Elem e)` - 在优先队列尾部添加一个元素`e`，该元素会被自动调整到正确的位置以保持优先级顺序。
3. `pop()` - 移除并返回优先队列头部的最大元素，即优先级最高的元素。
4. `top()` - 返回优先队列头部的最大元素，但不移除。
5. `size()` - 返回优先队列中元素的数量。
**改变排列顺序**
默认情况下，`priority_queue`使用大顶堆实现，即头部元素是最大值。若需实现小顶堆（头部元素是最小值），可以通过指定比较函数来实现：
1. 对于基本类型，如`int`，可以使用`greater<int>`作为比较函数，例如：
```cpp
priority_queue<int, vector<int>, greater<int>> Q;
```
2. 对于自定义数据类型，需要重载`<`运算符以指定元素的比较规则。可以是成员函数或友元函数来实现。不重载将导致编译错误，因为`priority_queue`内部依赖`<`操作符进行元素排序。
**使用范例**
以下是一个简单的`priority_queue`使用示例，向队列中压入数据，然后按优先级顺序出队并打印：
```cpp
#include <queue>
#include <cstdio>
int main() {
priority_queue<int> a;
for (int i = 0; i < 10; i++) {
a.push(i * 2 - 5);
}
printf("优先队列的大小=%d\n", a.size());
while (!a.empty()) {
printf("%d\n", a.top());
a.pop();
}
return 0;
}
```
**带比较函数的示例（针对结构体）**
在处理自定义数据类型时，可以定义一个结构体并重载`operator()`来进行比较。例如，模拟排队过程，优先级高或名字靠前的人员优先出队：
```cpp
struct Node {
char szName[20];
int priority;
Node(int pri, char* name) : priority(pri), strcpy(szName, name) {}
};
struct NodeCmp {
bool operator()(const Node& n1, const Node& n2) {
if (n1.priority == n2.priority) {
return strcmp(n1.szName, n2.szName) < 0;
}
return n1.priority < n2.priority;
}
};
// 然后可以创建一个使用NodeCmp比较函数的优先队列
priority_queue<Node, vector<Node>, NodeCmp> pq;
```
这个例子中，`NodeCmp`结构体重写了`operator()`，用于比较两个`Node`对象，根据优先级和名字进行排序。
`STL`的`priority_queue`提供了一种方便的方式来处理具有优先级的数据，无论是处理基本类型还是自定义类型，都能通过适当的方式灵活地设置优先级顺序。在实际编程中，合理利用优先队列可以提高代码的效率和可读性。
- 1
- 2
前往页