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

Question

如何使用 <algorithm>

中的 make_heap 方法创建最小堆

从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 函数参数 ，即你的对象。

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

How to use make_heap to create a min heap in c++

c++

heap

c++11

c++14