c++ - make_heap() 函数的算法在

Question

我只是在 C++ 中试验 make_heap() 函数。以下是我在每次调用 bool predicate() 时通过打印它们来跟踪正在比较的元素的代码。

#include <iostream>
#include <algorithm>
using namespace std;

// bool predicate function to make a min heap
bool predicate(int a, int b){
    cout << a << "  " << b << endl;
    if(a >= b){ return 1; }
    return 0;
}


int main(){
    int arr[] = {3,2,1,-1,-2};
    make_heap(arr, arr+5, predicate);
    return 0;
}

我得到的输出是：
-2 -1
-2 2
1 -2
2 -1
-1 3

但我期待以下输出，同时考虑标准算法：
-2 -1
-2 2
1 -2
3 -2
2 -1
-1 3

有什么帮助吗？

Answer 1

我不会说有一种足够标准化的算法，以至于您期望执行特定的比较集。标准化的是算法的复杂性，只要比较的次数是线性的，你就可以了。此外，就比较次数而言，它似乎stl比你表现得更好，所以你不必担心。

正如评论中所建议的那样，您始终可以阅读std::make_heap编译器使用的实现代码，但不能保证相同的实现将用于stl.