C++的std::priority_queue怎么实现最小堆_C++优先队列自定义比较器示例-C++-PHP中文网

C++的std::priority_queue怎么实现最小堆_C++优先队列自定义比较器示例

下次还敢

发布： 2025-11-06 16:23:31

原创

816人浏览过

默认情况下，C++的std::priority_queue是最大堆，通过使用std::greater<int>可实现基础类型的最小堆；处理自定义类型时，需定义比较结构体，如重载operator()并返回a.age > b.age以实现按年龄升序的最小堆，注意lambda不能直接用于模板参数。

c++的std::priority_queue怎么实现最小堆_c++优先队列自定义比较器示例

默认情况下，C++ 的 std::priority_queue 是一个最大堆（即顶部元素是最大的）。如果需要实现最小堆，可以通过自定义比较器来改变其行为。

使用 std::greater 实现最小堆

最简单的方法是使用 std::greater 作为比较函数对象。适用于基础类型如 int、double 等。

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // std::greater

示例代码：

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

min_heap.push(10);
min_heap.push(5);
min_heap.push(20);

while (!min_heap.empty()) {
std::cout << min_heap.top() << " ";
min_heap.pop();
}
// 输出: 5 10 20

自定义结构体 + 自定义比较器

当处理自定义类型时，比如结构体或类，可以定义自己的比较逻辑。

立即学习“C++免费学习笔记（深入）”；

struct Person {
  std::string name;
  int age;
  Person(std::string n, int a) : name(n), age(a) {}
};

希望按年龄从小到大排序（最小堆），可以写仿函数（函数对象）：

Calliper 文档对比神器

文档内容对比神器

查看详情

struct CompareAge {
  bool operator()(const Person& a, const Person& b) {
    return a.age > b.age; // 注意：这里用 > 实现最小堆
  }
};

std::priority_queue<Person, std::vector<Person>, CompareAge> pq;

示例使用：

pq.push(Person("Alice", 30));
pq.push(Person("Bob", 25));
pq.push(Person("Charlie", 35));

while (!pq.empty()) {
std::cout << pq.top().name << " " << pq.top().age << "\n";
pq.pop();
}
// 输出: // Bob 25 // Alice 30 // Charlie 35