首页c++ priority_queue最小堆

c++ priority_queue最小堆

时间: 2025-01-30 17:42:32 浏览: 42

### C++ 中使用 `priority_queue` 实现最小堆在 C++ 的标准模板库 (STL) 中，`std::priority_queue` 默认是一个最大堆。为了创建一个最小堆，可以通过指定第三个模板参数来改变比较逻辑。 #### 使用 `std::greater<T>` 创建最小堆通过传递 `std::greater<int>` 作为第三模板参数可以轻松实现这一点： ```cpp #include <queue> #include <iostream> int main() { // 声明一个存储 int 类型的最小堆 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 插入元素到最小堆中 minHeap.push(10); minHeap.push(20); minHeap.push(5); // 输出最小堆中的元素 while (!minHeap.empty()) { std::cout << "Top element is : " << minHeap.top() << '\n'; minHeap.pop(); } return 0; } ``` 这段代码展示了如何声明并操作一个整数类型的最小堆[^1]。当向队列中添加新项时，它会自动调整内部结构以保持最小堆属性——即根节点总是当前集合中最小的元素。对于其他数据类型（如浮点数或字符串），只需相应更改第一个模板参数即可。例如，要建立一个保存双精度数值的最小堆，则应写作: ```cpp std::priority_queue<double, std::vector<double>, std::greater<double>> ``` 同样地，如果希望处理自定义对象而非基本数据类型，那么还需要确保这些对象支持 `<` 运算符重载以便于比较操作正常工作[^4]。

阅读全文