C++ STL 中的优先队列 |21xrx.com

C++ STL 中的优先队列

2023-07-10 10:53:34 深夜i -- --

C++ STL 优先队列堆比较函数

C++ STL 中的优先队列是一种数据结构，用于存储和访问按优先级排序的元素。它是通过堆（heap）实现的，堆是一种特殊的树状数据结构，具有以下两个性质：

1. 堆一般用二叉树表示，并满足根节点的值小于（或大于）其子树的每个节点的值。

2. 堆的根节点表示优先级最高的元素。

优先队列是一种使用了堆的抽象数据类型，它支持在 O(log n) 的时间复杂度内插入一个元素和查找当前优先级最高的元素。由于堆是一种完全二叉树，因此我们可以使用数组来实现堆。在 C++ STL 中，使用 std::priority_queue 实现了优先队列的抽象数据类型。

std::priority_queue 可以按数值升序（默认情况下）或降序（通过将第二个模板参数设置为 std::vector , std::greater ）排序。当我们向优先队列中插入新元素时，C++ STL 会自动根据元素的优先级调整元素的位置，使得优先级最高的元素总是位于堆的根节点。当我们希望访问当前的最高优先级元素时，只需调用 std::priority_queue 中的 top() 方法即可。

为方便使用，而不是每次通过 top() 方法来获取最大值，我们可以实现一个自定义比较器，例如对于本例中实现最小值的优先队列的情况，使用 std::greater 的参数类型。

实现自定义比较器很简单，我们只需提供一个比较函数，该函数接受两个参数，并返回 bool 值，用于指示两个元素之间的指定关系。当第一个参数按照此关系小于第二个参数时，返回 true，否则返回 false。这个比较函数可以作为 std::priority_queue 的第三个参数传递。

下面是使用 std::priority_queue 实现一个最大值的优先队列的代码示例：


#include <iostream>
#include <queue>
int main()
{
  std::priority_queue<int> max_heap;
  for (int n : 2)
    max_heap.push(n);
  while (!max_heap.empty())
  {
    std::cout << max_heap.top() << " ";
    max_heap.pop();
  }
  std::cout << std::endl;
  return 0;
}

输出结果：

9 8 7 6 5 4 3 2 1 0

可以看到，输出结果是按照逆序排列的，即按照最大值排序。与 std::priority_queue 相关的更多信息可以在 C++ STL 中找到。

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

下一篇: 如何将Dev-C++ 5.11设置为中文版？

评论区

()

相似文章