c++priority_queue<

### C++ 中 `priority_queue` 的用法与实现 #### 使用方法 在 C++ 标准库中，`std::priority_queue` 是一种容器适配器，默认基于最大堆（max-heap），用于维护一组元素并始终提供当前的最大值。其定义位于头文件 `<queue>` 中。 以下是基本的声明方式及其参数说明： ```cpp #include <queue> template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; ``` 其中： - **T**: 存储的数据类型。 - **Container**: 底层使用的容器，默认为 `std::vector`。 - **Compare**: 定义比较逻辑，默认是最小值优先 (`std::less`) 表示最大堆；如果希望最小值处于顶部，则可以使用 `std::greater` 来构建最小堆[^1]。 #### 基本操作 下面列举了一些常用的成员函数以及它们的功能： | 函数名 | 描述 | |--------------|----------------------------------------------------------------------| | `push(x)` | 将新元素 `x` 添加到队列中，并保持堆属性 | | `top()` | 返回具有最高优先级的元素（即堆顶）。注意此操作不会移除该元素 | | `pop()` | 移除具有最高优先级的元素 | | `empty()` | 如果队列为空则返回 true | | `size()` | 返回队列中的元素数量 | 这些功能可以通过如下代码片段展示出来： ```cpp #include <iostream> #include <queue> int main() { std::priority_queue<int> pq; // Insert elements into the priority queue. pq.push(1); pq.push(5); pq.push(3); // Accessing top element of the priority queue. std::cout << "Top Element: " << pq.top() << "\n"; // Remove an element from the priority queue. pq.pop(); // Check size after popping one element. std::cout << "Size After Pop: " << pq.size() << "\n"; return 0; } ``` #### 自定义比较器 为了创建一个按升序排列的小根堆而非默认的大根堆，我们可以自定义比较器。例如，在处理结构体或者对象时尤为有用。这里给出如何通过 lambda 或者单独定义类作为比较器的例子: ##### Lambda Comparator Example: ```cpp auto cmp = [](const int a, const int b) -> bool {return a > b;}; std::priority_queue<int,std::vector<int>, decltype(cmp)> minHeap(cmp); minHeap.push(78); minHeap.push(-9); // ... ``` ##### Class-Based Comparator Example: ```cpp struct Comp { bool operator()(const int lhs, const int rhs)const{ return lhs >= rhs; // For Min Heap } }; std::priority_queue<int,std::vector<int>,Comp> customPq; customPq.emplace(42); // Emplace is similar to push but more efficient when constructing objects inside containers directly. ``` 以上两种形式均实现了从小到大排序的小根堆[^2]。 #### 实现细节 内部实现上，标准模板库(STL)里的 `std::priority_queue` 并未暴露具体数据结构给开发者查看修改，但是它通常采用二叉堆(binary heap)，因为这种树形结构非常适合动态集合的操作需求——插入删除的时间复杂度均为 O(log n)[^3]. 另外值得注意的是，虽然 STL 提供了方便易用的接口封装好的 `std::priority_queue`, 若有特殊场景下需要更灵活控制比如支持随机访问节点调整权重等情况的话，可能就需要自己手动去实现类似的机制类似于引用材料提到的部分宏定义辅助完成链表式的双端指针管理方案[^4].