C++ 中的 priority_queue

C++ 中的 priority_queue

priority_queue 是 C++ STL（标准模板库）中的一个重要容器。它类似于普通的队列，但有一些关键区别：

1. 队首元素总是优先级最高的：在队列中，元素按照优先级参数排序，最小（或者最大）元素总是在队列的前端，并且会在每次出队的时候被删除。
2. 底层使用堆来实现：priority_queue 默认使用 vector 作为其底层存储数据的容器，然后使用堆的向上调整和向下调整算法将 vector 中的元素构造成堆的结构。

在 C++ 中，priority_queue 的模板定义如下：

template<
    class T,
    class Container = vector<T>,
    class Compare = less<typename Container::value_type>
> class priority_queue;

其中：

• T 是存储在队列中的元素类型。
• Container 是底层容器类型，默认为 vector。
• Compare 是一个可选的比较器，用于确定元素的顺序。默认情况下，它是 std::less，表示大顶堆，你也可以使用 std::greater 来创建小顶堆。

常见用法

1. 定义 priority_queue：

   要使用优先队列，首先添加头文件 #include <queue>，并在头文件下面加上 using namespace std;，然后就可以定义一个 priority_queue 了。其定义的写法和其他 STL 容器相同，typename 可以是任意基本数据类型或容器：

   priority_queue<typename> name;
   

2. 访问队首元素：

   与队列不同的是，优先队列没有 front() 函数和 back() 函数，而只能通过 top() 函数来访问队首元素（也可以称为堆顶元素），即优先级最高的元素。

   示例如下：

   #include <queue>
   using namespace std;
   
   int main() {
       priority_queue<int> q;
       q.push(3);
       q.push(4);
       q.push(1);
       printf("%d\n", q.top());
       return 0;
   }
   

   输出结果：4

3. 常用函数实例解析：

   • push(x): 将元素 x 入队，时间复杂度为 O(logN)，其中 N 为当前优先队列中的元素个数。
   • top(): 获得队首元素（即堆顶元素），时间复杂度为 O(1)。
   • pop(): 令队首元素（即堆顶元素）出队，时间复杂度为 O(logN)，其中 N 为当前优先队列中的元素个数。
   • empty(): 检测优先队列是否为空，返回 true 则空，返回 false 则非空，时间复杂度为 O(1)。
   • size(): 返回优先队列内元素的个数，时间复杂度为 O(1)。

4. 内元素优先级的设置：

   如何定义优先队列内元素的优先级是运用好优先队列的关键。对于基本数据类型，数字大的优先级越高；而对于结构体类型，可以重载小于号 < 来自定义优先级。