priority_queue<int, vector<int>, greater<int>> min_heap; 小顶堆为什么用greater?
时间: 2024-09-06 22:03:28 浏览: 46
stl.zip_SGI STL源码
`std::priority_queue<int, std::vector<int>, std::greater<int>>` 使用 `std::greater<int>` 是因为小顶堆(min heap)的特性是它的根节点总是具有最小的关键值。`std::greater<int>` 是一个比较函数,它定义了一个降序关系,即较大的元素被认为是“更好”的。这样,在插入元素时,它们会被调整到满足堆的性质,即每个父节点的值都小于或等于其子节点的值。
如果使用默认的 `<` 运算符(升序关系),那么就会形成一个大顶堆,而非小顶堆。因此,为了创建一个小顶堆,我们需要指定 `std::greater<int>` 来实现元素的反向排序。
例如:
```cpp
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
// 插入元素
min_heap.push(5);
min_heap.push(3);
min_heap.push(7);
// 最小值始终在堆顶
std::cout << "Minimum element: " << min_heap.top() << '\n'; // 输出: 3
```
阅读全文