c++ - 如何使用 make_heap 在 C++ 中创建最小堆

Question

如何使用 make_heap 创建最小堆<algorithm> 中的方法

来自documentation它说，我们可以传入第三个参数 Compare comp 那是一个

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to be less than the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

所以我尝试按如下方式传入一个函数对象

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

struct myComp {

    bool operator() (const pair<int, char>& lhs, const pair<int, char>& rhs) {
        return lhs.first > rhs.first;
    }
};

int main() {
    vector< pair<int, char> > Q;
    Q.push_back( pair<int, char>(10, 'c') );
    Q.push_back( pair<int, char>(123, 'a') );
    Q.push_back( pair<int, char>(2, 'd') );
    Q.push_back( pair<int, char>(9, 'f') );
    Q.push_back( pair<int, char>(81, 'b') );
    Q.push_back( pair<int, char>(4, 'e') );

    make_heap(Q.begin(), Q.end(), myComp);

    pop_heap(Q.begin(), Q.end());

    cout << Q.back().first << ", " << Q.back().second << endl;
    Q.pop_back();

    return 0;
}

我收到以下错误

jdoodle.cpp: In function 'int main()':
jdoodle.cpp:25:38: error: expected primary-expression before ')' token
  make_heap(Q.begin(), Q.end(), myComp);
                                      ^

我真的不明白这是什么意思，我做错了什么？

Answer 1

myComp 是一个类型名，而 std::make_heap 是一个函数(模板)，要调用它你需要传递一个对象。因此，创建一个该类型的对象。

make_heap(Q.begin(), Q.end(), myComp{});

{} 将初始化您传递的 myComp 对象。

当您阅读文档时，Compare 是仿函数的推导类型，但请注意函数模板需要一个comp 函数参数，那是你的对象。