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

Question

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

我尝试了下面的代码（来自 geeksforgeeks 的一点修改）：

#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() 是尾后迭代器。 IE。它不指向实际值，取消引用它是非法的。

我认为您试图执行以下操作：

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

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

话虽这么说，从评论中的讨论来看，OP 的问题实际上是 "min heap in stl without writing a comparator"，两者略有不同，并导致了截然不同的答案。

STL 提供了现成的模板化比较器来处理这些情况。原因是拥有更少、更灵活的算法会更干净。 API 表面越低越好。

您只需执行以下操作：

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

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

min heap in stl without comparator

c++

heap