C++中优先队列priority_queue详解(定义、基本用法、常用操作、实例)

在C++标准模板库（STL）中，priority_queue 是一种特殊的容器适配器，用于实现优先级队列。它提供了一种按照特定顺序存储元素的方式，使得每次访问队列时都能获得具有最高优先级的元素。本文将详细介绍 priority_queue 的定义、基本用法、常用操作以及一些实际应用示例，帮助开发者更好地理解和使用这一强大的工具。

一、优先队列 priority_queue 的定义

定义：priority_queue 是C++标准模板库中的一个容器适配器，用于实现优先级队列。

头文件：#include <queue>

模板参数：第一个参数：存储的元素类型。

第二个参数：底层容器类型，默认为 vector。

第三个参数：比较函数，默认为 greater（小顶堆）。

优先级队列：priority_queue 按照元素的优先级进行排序，每次访问时都会返回具有最高优先级的元素。

动态调整：priority_queue 会自动调整内部元素的顺序，确保每次访问时都能获得具有最高优先级的元素。

支持多种数据类型：priority_queue 可以存储各种数据类型，如整数、浮点数、字符串等。

与 vector 的区别：vector 是一个动态数组，而 priority_queue 是一个基于堆的优先级队列。

与 deque 的区别：deque 是一个双端队列，而 priority_queue 是一个基于堆的优先级队列。

与 list 的区别：list 是一个双向链表，而 priority_queue 是一个基于堆的优先级队列。

二、优先队列 priority_queue 的基本用法

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
return0;
}

解释：上述代码声明了一个存储整数的优先队列 pq。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
return0;
}

解释：上述代码向优先队列 pq 中插入了三个整数 5、3 和 8。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
cout<<"最高优先级元素:"<<pq.top()<<endl;
return0;
}

解释：上述代码访问了优先队列 pq 中的最高优先级元素，并输出其值。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
cout<<"最高优先级元素:"<<pq.top()<<endl;
pq.pop();
cout<<"删除后最高优先级元素:"<<pq.top()<<endl;
return0;
}

解释：上述代码删除了优先队列 pq 中的最高优先级元素，并输出删除后的最高优先级元素。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
pq.pop();
pq.pop();
pq.pop();
if(pq.empty()){
cout<<"队列已清空"<<endl;
}
return0;
}

解释：上述代码清空了优先队列 pq，并检查是否为空。

三、优先队列 priority_queue 的常用操作

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
cout<<"队列大小:"<<pq.size()<<endl;
return0;
}

解释：上述代码获取了优先队列 pq 的大小。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
if(pq.empty()){
cout<<"队列为空"<<endl;
}else{
cout<<"队列不为空"<<endl;
}
return0;
}

解释：上述代码检查了优先队列 pq 是否为空。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq1;
priority_queue<int>pq2;
pq1.push(5);
pq1.push(3);
pq1.push(8);
pq2.push(1);
pq2.push(4);
pq2.push(7);
pq1.swap(pq2);
cout<<"交换后pq1:";
while(!pq1.empty()){
cout<<pq1.top()<<"";
pq1.pop();
}
cout<<endl;
cout<<"交换后pq2:";
while(!pq2.empty()){
cout<<pq2.top()<<"";
pq2.pop();
}
return0;
}

解释：上述代码交换了两个优先队列 pq1 和 pq2 的内容。

示例：

#include<iostream>
#include<queue>
usingnamespacestd;
intmain(){
priority_queue<int>pq;
pq.push(5);
pq.push(3);
pq.push(8);
priority_queue<int>pq_copy=pq;
cout<<"优先队列内容:";
while(!pq_copy.empty()){
cout<<pq_copy.top()<<"";
pq_copy.pop();
}
return0;
}

解释：上述代码通过迭代器遍历了优先队列 pq 的内容。

四、优先队列 priority_queue 的实例

场景：在一个任务调度系统中，需要按照任务的优先级依次执行任务。

示例：

#include<iostream>
#include<queue>
#include<string>
usingnamespacestd;
structTask{
stringname;
intpriority;
booloperator<(constTask&other)const{
returnpriority<other.priority;//小顶堆
}
};
intmain(){
priority_queue<Task>taskQueue;
taskQueue.push({"TaskA",3});
taskQueue.push({"TaskB",1});
taskQueue.push({"TaskC",2});
while(!taskQueue.empty()){
TaskcurrentTask=taskQueue.top();
taskQueue.pop();
cout<<"执行任务:"<<currentTask.name<<",优先级:"<<currentTask.priority<<endl;
}
return0;
}

解释：上述代码模拟了一个任务调度系统，按照任务的优先级依次执行任务。

场景：在一个路径规划系统中，需要按照路径的距离依次选择路径。

示例：

#include<iostream>
#include<queue>
#include<vector>
usingnamespacestd;
structNode{
intid;
doubledistance;
booloperator<(constNode&other)const{
returndistance>other.distance;//小顶堆
}
};
intmain(){
priority_queue<Node>pathQueue;
pathQueue.push({1,10.5});
pathQueue.push({2,5.2});
pathQueue.push({3,8.9});
while(!pathQueue.empty()){
NodecurrentNode=pathQueue.top();
pathQueue.pop();
cout<<"选择路径:"<<currentNode.id<<",距离:"<<currentNode.distance<<endl;
}
return0;
}

解释：上述代码模拟了一个路径规划系统，按照路径的距离依次选择路径。

场景：在一个事件处理系统中，需要按照事件的时间戳依次处理事件。

示例：

#include<iostream>
#include<queue>
#include<string>
usingnamespacestd;
structEvent{
stringname;
inttimestamp;
booloperator<(constEvent&other)const{
returntimestamp<other.timestamp;//小顶堆
}
};
intmain(){
priority_queue<Event>eventQueue;
eventQueue.push({"EventA",3});
eventQueue.push({"EventB",1});
eventQueue.push({"EventC",2});
while(!eventQueue.empty()){
EventcurrentEvent=eventQueue.top();
eventQueue.pop();
cout<<"处理事件:"<<currentEvent.name<<",时间戳:"<<currentEvent.timestamp<<endl;
}
return0;
}

解释：上述代码模拟了一个事件处理系统，按照事件的时间戳依次处理事件。

priority_queue 是C++标准模板库中的一个重要工具，用于实现优先级队列。本文详细介绍了 priority_queue 的定义、基本用法、常用操作以及一些实际应用示例。通过本文的介绍，开发者可以更好地理解和应用 priority_queue，提高C++编程的效率和准确性。希望本文提供的信息能够帮助开发者更好地掌握 priority_queue 的使用技巧，避免在实际开发中遇到问题。

以上就是php小编整理的全部内容，希望对您有所帮助，更多相关资料请查看php教程栏目。