C++ 优先队列 |21xrx.com

C++ 优先队列

2023-06-29 08:13:23 深夜i -- --

C++ 优先队列数据结构最小堆最大堆

C++ 中的优先队列（Priority Queue）是一种特殊的数据结构，它能够自动将元素以优先级的顺序进行排序和调整，优先级高的元素会被优先处理。优先队列可以用来实现各种算法，包括最短路径算法、最小生成树算法、贪心算法等。

C++ 中的优先队列属于 STL（标准模板库）中的一部分，它具有以下特点：

1. 内部实现为二叉堆（Binary Heap），即底层用数组实现，以完全二叉树的形式存储。

2. 支持插入（Push）、删除（Pop）和获取队首元素（Top）等操作，这些操作的时间复杂度均为 O(log n)。

3. 默认情况下，元素按照从大到小的顺序排序，也可以通过自定义比较器来改变排序方式。

4. 可以支持任何数据类型，包括内置类型和自定义类型。如果自定义类型，需要重载比较运算符（<）。

下面是一个简单的示例，演示了如何使用 C++ 的优先队列来实现元素的插入、删除和获取队首元素操作。


#include <queue>
#include <iostream>
using namespace std;
int main() {
  // 创建优先队列
  priority_queue<int> pq;
  // 插入元素
  pq.push(10);
  pq.push(50);
  pq.push(30);
  // 获取队首元素
  cout << "队首元素为：" << pq.top() << endl;
  // 删除队首元素
  pq.pop();
  cout << "队首元素为：" << pq.top() << endl;
  // 获取队列大小
  cout << "队列大小为：" << pq.size() << endl;
  return 0;
}

上述代码创建了一个优先队列，插入了三个元素，分别是 10、50 和 30，然后获取队首元素，删除队首元素，再次获取队首元素，最后输出队列大小。运行结果如下：

队首元素为：50 队首元素为：30 队列大小为：1

可以看到，输出的队首元素依次为 50 和 30，队列大小为 1，这是因为每次删除队首元素后，队列大小都会减少 1。

总之，C++ 中的优先队列是一种非常有用的数据结构，可以方便地实现各种算法和数据处理任务。掌握了优先队列的使用方法，将对 C++ 编程有很大的帮助。

上一篇: idea打包java可执行jar包

下一篇: Dev C++无法完全显示结果

评论区

()

相似文章