priority_queue<int, vector<int>, greater<int>> min_heap; 小顶堆为什么用greater？

std::priority_queue<int, std::vector<int>, std::greater<int>> 使用 std::greater<int> 是因为小顶堆（min heap）的特性是它的根节点总是具有最小的关键值。std::greater<int> 是一个比较函数，它定义了一个降序关系，即较大的元素被认为是“更好”的。这样，在插入元素时，它们会被调整到满足堆的性质，即每个父节点的值都小于或等于其子节点的值。
如果使用默认的 < 运算符（升序关系），那么就会形成一个大顶堆，而非小顶堆。因此，为了创建一个小顶堆，我们需要指定 std::greater<int> 来实现元素的反向排序。
例如：
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
登录后复制

相关问题

为什么你说 priority_queue<int, vector<int>, greater<int> > min_heap;是小根堆？

这是因为在C++标准库中，priority_queue默认使用的是大根堆，即元素值大的在堆顶。为了使用小根堆，我们需要指定priority_queue的三个参数：元素类型、容器类型、比较函数类型。其中，比较函数类型可以通过传递greater来指定，它表示要使用的是从小到大的排序方式，从而使得堆顶元素始终为最小值，这样就实现了小根堆的效果。

priority_queue<int,vector<int>,greater<int> > heap;

priority_queue<int,vector,greater > heap; 是一个定义小根堆的优先队列，它存储整数类型的元素，并按照从小到大的顺序进行排序。这意味着在这个小根堆中，最小的元素将位于队列的顶部，而较大的元素将放置在较低的位置。你可以使用这个优先队列来实现一些需要按照特定顺序处理元素的算法。