没有比较器的stl中的最小堆

Question

我刚刚开始使用STL，目前正在使用堆。我只想知道是否有一种方法可以在没有比较器的情况下实现c++/cpp中的最小堆。

我尝试了以下代码(对极客的一些修改)：

#include<iostream>
#include<algorithm> // for heap 
#include<vector>
using namespace std;

int main()
{
    // initializing vector;
    vector<int> vi = { 1, 6, 7, 9, 11, 4 };

    make_heap(vi.end(), vi.begin()); // swapped the start and end points

    cout << "The minimum element of heap is : ";
    cout << vi.front() << endl;

}

输出是：1

我也在其他测试用例中尝试过这一点，而且它似乎运行良好。只是想知道这在逻辑上是否正确？这是一个很好的练习吗？

Answer 1

首先，你的代码：

make_heap(vi.end(), vi.begin());

这导致了未定义的行为，因为vi.end()是一个过去的迭代器。也就是说，它没有指出一个实际的价值，取消引用它将是非法的。

我认为你试图做以下几件事：

make_heap(vi.rbegin(), vi.rend());

但这是行不通的，因为生成的堆仍然是一个max_heap。

尽管如此，从评论中的讨论来看，OP的问题实际上是“没有编写比较器的stl中的最小堆”，这是微妙的不同，并导致了一个非常不同的答案。

STL提供现成的模板比较器来处理这些情况.理由是，使用更少、更灵活的算法要干净得多。API表面越低越好。

你所要做的就是：

make_heap(vi.begin(), vi.end(), std::greater<>());