admin管理员组文章数量:1623784
一、介绍
priority_queue是C++标准库中提供的一种容器适配器,它提供了一种存储和操作元素的方式,确保优先级最高的元素始终位于队列的前面。它可以在运行时自动地保持其元素有序。其内部实现了一个堆(heap),具有以下性质:
最大堆(max heap):根节点的值大于等于其子节点的值。
最小堆(min heap):根节点的值小于等于其子节点的值。
priority_queue中的元素根据它们的优先级进行排序,这是由在声明时提供的比较函数决定的。默认情况下,priority_queue使用std::less按升序排序元素,其中T是被存储元素的类型。
priority_queue容器支持以下操作:
push(): 将新元素插入到优先级队列中。
pop(): 从优先级队列中删除最高优先级的元素。
top(): 返回位于队列前面的最高优先级的元素。
empty(): 检查优先级队列是否为空。
size(): 返回优先级队列中元素的数量。
需要注意的是,priority_queue并不提供遍历容器中所有元素的方式,因为它被设计为只允许访问位于队列前面的最高优先级的元素。如果需要遍历所有元素,可以将priority_queue的元素复制到另一个容器中进行遍历。
参数说明:
std::priority_queue<T, Container, Compare>
其中,T 表示队列中元素的类型;Container 表示内部容器的类型,默认情况下是 std::vector;Compare 是一个可选的比较函数对象,用来指定元素的比较规则,如果不指定,则默认使用 std::less 来进行比较。
下面分别介绍 Container 和 Compare 两个参数。
Container
Container 是一个用于存储元素的内部容器类型,默认为 std::vector。它必须提供以下几个方法:
front():返回队列中第一个元素的引用。
push_back(const T& x):将元素 x 添加到容器的末尾。
pop_back():删除容器末尾的元素。
size():返回容器中元素的个数。
除了 std::vector,还可以使用其他类型的容器,例如 std::deque,或者用户自定义的容器类型。
Compare
Compare 是一个可选的比较函数对象,用来指定元素的比较规则。如果不指定,则默认使用 std::less 来进行比较,即使用 < 运算符来比较元素大小。如果想要创建一个最小堆,则可以指定 Compare 为 std::greater,即使用 > 运算符来比较元素大小。
比较函数对象需要实现一个接受两个元素的参数,返回一个 bool 类型的结果,表示第一个元素是否小于(或大于)第二个元素。例如:
struct Compare {
bool operator()(const T& lhs, const T& rhs) {
// 比较 lhs 和 rhs 的大小关系,返回结果
}
};
当我们指定 Compare 为 struct Compare 时,我们需要自己实现比较函数 operator(),来定义元素的比较规则。
二、demo
#include <queue>
#include <iostream>
using namespace std;
int main() {
priority_queue<int> max_heap;
// Insert elements into the heap
max_heap.push(10);
max_heap.push(20);
max_heap.push(15);
// Print the largest element in the heap
cout << "Largest element in the heap: " << max_heap.top() << endl;
// Remove the largest element from the heap
max_heap.pop();
// Print the new largest element in the heap
cout << "New largest element in the heap: " << max_heap.top() << endl;
return 0;
}
输出结果:
Largest element in the heap: 20
New largest element in the heap: 15
三、自定义排序
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <functional>
using namespace std;
struct data_info
{
string data;
int line;
};
struct cmp1
{
bool operator () (data_info a,data_info b)
{
return a.line < b.line;
}
};
void test_priority_queue()
{
priority_queue<data_info, vector<data_info>, cmp1> data_queue;
data_queue.push({"123", 0});
data_queue.push({"852", 1});
data_queue.push({"2341", 2});
data_queue.push({"789", 1});
data_queue.push({"1233", 0});
data_queue.push({"963", 1});
data_queue.push({"1232", 0});
data_queue.push({"756", 1});
data_queue.push({"2342", 2});
data_queue.push({"1231", 0});
data_queue.push({"234", 2});
data_queue.push({"741", 2});
while(!data_queue.empty())
{
cout << data_queue.top().data << " " << data_queue.top().line<< endl;
data_queue.pop();
}
}
int main()
{
test_priority_queue();
return 0;
}
输出结果
2341 2
741 2
2342 2
234 2
852 1
963 1
789 1
756 1
1232 0
1233 0
1231 0
123 0
需要注意的是:如果priority_queue中有多个元素具有相同的优先级,它们的排列方式是不确定的。这是因为priority_queue使用堆数据结构来维护元素的优先级,堆的性质决定了同一优先级的元素之间没有明确的顺序。
在默认情况下,priority_queue使用std::less作为比较函数来比较元素的优先级,这将导致具有相同优先级的元素以相反的顺序排列,即后插入的元素将排在前面。如果需要更精确的控制元素之间的顺序,可以提供自定义比较函数来指定元素之间的优先级关系。
本文标签: 优先级队列顺序数据priorityqueue
版权声明:本文标题:C++ 优先队列priority_queue(同一优先级数据顺序) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728895070a1178305.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论