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

C++优先队列

2023-07-10 05:31:05 深夜i 23 0

C++ 优先队列算法数据结构 STL

C++中的优先队列是一种特殊的队列，它在添加元素时可以根据一定的规则自动排序。优先队列的应用广泛，如 Dijkstra 算法、Huffman 编码等。

C++标准库中的优先队列容器是基于堆的实现，堆的定义是一棵树结构，每个节点都比子节点的值大（或小），且堆是一棵完全二叉树。由于堆的特性，插入和删除操作的时间复杂度是 O(log n)。

在C++中，std::priority_queue是优先队列的具体实现，它提供了一些成员函数，如push、pop、top、size、empty等，使其易于使用。在创建std::priority_queue时，必须指定元素类型和优先级比较函数。默认情况下，优先队列中的元素为大根堆，即优先级高的元素排在队列的前面。

下面是一个小的示例程序：

#include <iostream>
#include <queue>
using namespace std;
int main()
{
  priority_queue<int> max_heap; // 默认大根堆
  priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆
  for(int i=1; i<=10; i++)
  {
    max_heap.push(i);
    min_heap.push(i);
  }
  while(!max_heap.empty())
  {
    cout << max_heap.top() << " ";
    max_heap.pop();
  }
  cout << endl;
  while(!min_heap.empty())
  {
    cout << min_heap.top() << " ";
    min_heap.pop();
  }
  cout << endl;
  return 0;
}

这个程序使用了两个优先队列，一个是大根堆，一个是小根堆。在加入元素之后，分别输出堆顶元素并弹出，可以看到大根堆输出的是递减的序列，小根堆输出的是递增的序列。

C++中的优先队列是一种高效的数据结构，可以很方便地解决很多问题。在实际应用中，需要根据具体问题选择合适的优先级比较函数，才能得到最佳性能和正确的结果。

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

下一篇: 如何在Dev-C++中创建新项目

评论区

相似文章