1 std::priority_queue 应用于自定义数据结构
当应用于自定义数据结构时，std::priority_queue 的灵活性和可定制性可以得到充分体现。下面将详细讲解 std::priority_queue 如何与自定义数据结构结合使用。
自定义数据结构
首先，需要定义一个自定义数据类型，这可以是一个类或者结构体。这个自定义数据类型将作为 std::priority_queue 的元素类型。例如：
struct MyData {
int id;
double value;
// 可能还有其他成员变量和方法
// 构造函数、析构函数等（如果需要的话）
};
然后，可以使用这个比较对象来初始化 std::priority_queue：
std::priority_queue<MyData, std::vector<MyData>, CompareMyData> pq;
在这个例子中，std::priority_queue 使用 std::vector<MyData> 作为底层容器，并使用 CompareMyData 作为比较对象。这意味着队列中的元素将按照 CompareMyData 定义的优先级进行排序。
自定义数据结构
除了自定义比较函数或对象外，还可以指定一个自定义的底层容器来存储 std::priority_queue 的元素。这允许完全控制优先队列的行为和性能。例如，可以使用 std::deque 或其他容器类型作为底层容器。但需要注意的是，不是所有的容器类型都适合作为优先队列的底层容器，因为优先队列需要底层容器支持某些特定的操作（如随机访问迭代器）。
下面是一个完整的示例，展示了如何使用 std::priority_queue 与自定义数据结构 MyData 和自定义比较对象 CompareMyData：
#include <iostream>
#include <queue>
#include <vector>
struct MyData {
int id;
double value;
MyData(int id, double value) : id(id), value(value) {}
};
struct CompareMyData {
bool operator()(const MyData& a, const MyData& b) const {
return a.value < b.value; // 小于号表示大顶堆
}
};
int main()
{
std::priority_queue<MyData, std::vector<MyData>, CompareMyData> pq;
pq.push(MyData(1, 3.0));
pq.push(MyData(2, 1.0));
pq.push(MyData(3, 2.0));
while (!pq.empty()) {
MyData topElement = pq.top();
pq.pop();
std::cout << "ID: " << topElement.id << ", Value: " << topElement.value << std::endl;
}
return 0;
}
上面代码的输出为：
ID: 1, Value: 3
ID: 3, Value: 2
ID: 2, Value: 1
这个示例创建了一个 std::priority_queue，其中包含了自定义数据类型 MyData 的对象，并使用自定义比较对象 CompareMyData 来定义元素的优先级。然后，向队列中添加了一些元素，并逐个取出并打印它们的 id 和 value。由于使用了大顶堆，所以打印出的元素将按照 value 的降序排列。
2 std::priority_queue 的主要应用场景
下面是 std::priority_queue 的一些主要应用场景：
（1）任务调度与优先级管理
当有一系列任务需要按照优先级执行时，可以使用 std::priority_queue。例如，在操作系统或任务调度系统中，高优先级的任务会优先于低优先级的任务执行。通过将任务对象插入优先队列，并根据其优先级进行排序，可以方便地获取和执行最高优先级的任务。
（2）图算法中的优化
在图算法中，如 Dijkstra 算法用于寻找最短路径，或 Prim 算法用于寻找最小生成树时，std::priority_queue 可以用来高效地选择当前未访问节点中距离最短的节点。在这些算法中，优先队列用于维护一个待处理的节点集合，并根据它们的某种度量（如距离）进行排序。
（3）事件驱动系统
在事件驱动的系统中，事件可能按照不同的优先级触发。使用 std::priority_queue 可以确保高优先级的事件优先得到处理。例如，在游戏开发中，重要的用户输入事件（如按键操作）可能具有比背景动画更新更高的优先级。
（4）实时系统
在实时系统中，对时间敏感的任务需要快速响应。std::priority_queue 可以帮助系统按照任务的紧急程度或截止时间进行排序，从而确保关键任务得到及时处理。
（5）资源分配
当有限的资源需要分配给多个请求时，可以使用 std::priority_queue 来根据请求的优先级进行资源分配。例如，在服务器处理客户端请求时，可以根据请求的紧急程度或付费级别来分配计算资源。
（6）自定义数据结构的排序
当需要对自定义数据结构进行排序时，std::priority_queue 可以结合自定义比较函数或对象使用。这使得它成为处理具有复杂比较逻辑的数据结构的强大工具。例如，在模拟系统中，可能需要根据多个属性（如速度、位置等）来确定对象的优先级。
2.1 std::priority_queue 应用于任务调度与优先级管理
std::priority_queue 在任务调度与优先级管理中的应用非常直接且有效。以下是一个简单的示例，展示了如何使用 std::priority_queue 来实现一个基本的任务调度系统。
首先，定义一个 Task 结构体，其中包含任务的标识符、优先级以及需要执行的操作（这里用简单的函数指针代替）。然后，创建一个 CompareTask 结构体来定义任务的比较逻辑，即优先级高的任务应该排在优先队列的前面。
#include <iostream>
#include <queue>
#include <functional>
// 任务类型
struct Task {
int id;
int priority;
std::function<void()> action; // 执行的任务操作
Task(int id, int priority, std::function<void()> action)
: id(id), priority(priority), action(action) {}
};
// 比较任务优先级的结构体
struct CompareTask {
bool operator()(const Task& a, const Task& b) const {
// 返回 true 如果 a 的优先级低于 b 的优先级，这样 a 会被放在队列后面
return a.priority < b.priority;
}
};
int main()
{
// 创建一个最大堆的优先队列，根据任务的优先级排序
std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;
// 添加任务到队列中，每个任务都有一个唯一的 ID、优先级和要执行的操作
taskQueue.push(Task(1, 3, []() { std::cout << "Executing task 1 (priority 3)\n"; }));
taskQueue.push(Task(2, 1, []() { std::cout << "Executing task 2 (priority 1)\n"; }));
taskQueue.push(Task(3, 2, []() { std::cout << "Executing task 3 (priority 2)\n"; }));
// 执行任务，直到队列为空
while (!taskQueue.empty()) {
Task currentTask = taskQueue.top(); // 获取最高优先级的任务
taskQueue.pop(); // 从队列中移除该任务
currentTask.action(); // 执行任务的操作
}
return 0;
}
上面代码的输出为：
Executing task 1 (priority 3)
Executing task 3 (priority 2)
Executing task 2 (priority 1)
这个示例创建了一个 std::priority_queue，它使用 Task 结构体作为元素类型，并使用 CompareTask 结构体来定义任务的优先级比较逻辑。然后通过 std::function<void()> 来表示每个任务需要执行的操作，这使得任务可以包含任何我们想要执行的代码。
接下来向优先队列中添加了三个任务，每个任务都有不同的优先级。然后，使用一个循环来从队列中取出并执行任务，直到队列为空。由于这里使用了最大堆（即大顶堆），所以每次从队列中取出的都是当前优先级最高的任务。
运行这个程序，可以看到任务按照优先级的降序被执行。这就是 std::priority_queue 在任务调度与优先级管理中的一个简单应用。在实际应用中，任务可能包含更复杂的逻辑和操作，但这个示例提供了一个基本的框架和思路。
2.2 std::priority_queue 应用于 Dijkstra 算法
Dijkstra 算法是一个用于解决带权有向图中单源最短路径问题的算法。在 Dijkstra 算法中，std::priority_queue 是一个非常适合的数据结构，用于存储待处理的节点，并根据它们的当前最短距离进行排序。下面是一个使用 std::priority_queue 实现 Dijkstra 算法的示例：
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
// 用于存储边的结构体
struct Edge {
int dest;
int weight;
Edge(int d, int w) : dest(d), weight(w) {}
};
// Dijkstra算法实现
void dijkstra(vector<vector<Edge>>& graph, int src) {
int V = graph.size();
vector<int> dist(V, INT_MAX); // 存储从源点到各个顶点的最短距离
dist[src] = 0; // 源点到自身的距离为0
vector<bool> visited(V, false); // 标记节点是否被访问过
// 使用小顶堆，按照距离排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, src }); // 初始时将源点入队，距离为0
while (!pq.empty()) {
// 取出当前距离最短的节点
int u = pq.top().second;
pq.pop();
// 如果该节点已经被访问过，则跳过
if (visited[u]) continue;
visited[u] = true;
// 遍历与当前节点相邻的节点
for (const Edge& edge : graph[u]) {
int v = edge.dest;
int weight = edge.weight;
// 如果发现一条更短的路径，则更新距离，并将该节点入队
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push({ dist[v], v });
}
}
}
// 输出结果
cout << "Vertex \t\t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << "\t\t" << dist[i] << endl;
}
int main()
{
// 初始化图
int V = 5; // 顶点数量
vector<vector<Edge>> graph(V);
graph[0].push_back(Edge(1, 9));
graph[0].push_back(Edge(2, 6));
graph[0].push_back(Edge(4, 5));
graph[1].push_back(Edge(3, 15));
graph[2].push_back(Edge(3, 11));
graph[2].push_back(Edge(1, 2));
graph[3].push_back(Edge(4, 6));
// 调用Dijkstra算法
dijkstra(graph, 0); // 从顶点0开始
return 0;
}
上面代码的输出为：
Vertex Distance from Source
0 0
1 8
2 6
3 17
4 5
这个示例首先定义了一个Edge结构体来存储图的边信息。然后，实现了 Dijkstra 算法。算法开始时，初始化所有顶点到源点的距离为无穷大（INT_MAX），除了源点到自身的距离为 0。这里使用一个 visited 数组来跟踪哪些节点已经被处理过。
priority_queue 用于存储待处理的节点对，每个节点对包含一个距离值和一个顶点索引。队列根据距离值进行排序，因此每次从队列中取出的都是当前距离最短的节点。
在算法的主体部分，不断从队列中取出距离最短的节点，并更新其相邻节点的距离。如果找到了一条更短的路径，就更新该节点的距离，并将其重新加入队列。
最后，输出每个顶点到源点的最短距离。
3 实现一个简单的 std::priority_queue
可以使用一个数组或动态数组（如 std::vector）作为底层存储，并手动实现堆的基本操作，如插入元素、删除顶部元素和调整堆结构。以下是一个简化版的 std::priority_queue 实现，仅支持最大堆（即顶部元素总是最大的）。
#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::swap
template <typename T>
class SimplePriorityQueue {
private:
std::vector<T> elements;
// 调整堆结构，确保父节点总是大于或等于其子节点
void siftUp(int index) {
int parent = (index - 1) / 2;
while (index > 0 && elements[parent] < elements[index]) {
std::swap(elements[parent], elements[index]);
index = parent;
parent = (index - 1) / 2;
}
}
// 调整堆结构，确保父节点总是大于或等于其子节点
void siftDown(int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index;
if (leftChild < elements.size() && elements[leftChild] > elements[largest]) {
largest = leftChild;
}
if (rightChild < elements.size() && elements[rightChild] > elements[largest]) {
largest = rightChild;
}
if (largest != index) {
std::swap(elements[index], elements[largest]);
siftDown(largest);
}
}
public:
// 插入元素
void push(const T& value) {
elements.push_back(value);
siftUp(elements.size() - 1);
}
// 删除顶部元素
void pop() {
if (elements.empty()) {
throw std::out_of_range("Priority queue is empty");
}
elements[0] = elements.back();
elements.pop_back();
siftDown(0);
}
// 返回顶部元素，但不删除
T top() const {
if (elements.empty()) {
throw std::out_of_range("Priority queue is empty");
}
return elements[0];
}
// 检查队列是否为空
bool empty() const {
return elements.empty();
}
// 获取队列大小
size_t size() const {
return elements.size();
}
};
int main()
{
SimplePriorityQueue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << "Top element is: " << pq.top() << std::endl; // 输出 4
pq.pop();
std::cout << "Top element after pop is: " << pq.top() << std::endl; // 输出 3
return 0;
}
上面代码的输出为：
Top element is: 4
Top element after pop is: 3
在这个实现中，SimplePriorityQueue 类使用 std::vector 来存储元素。push 方法用于向队列中添加元素，并在添加后通过 siftUp 方法调整堆的结构。pop 方法用于删除顶部元素，并通过 siftDown 方法重新调整堆的结构。top 方法返回顶部元素的值。empty 和 size 方法分别用于检查队列是否为空和获取队列的大小。