Алгоритм функции make_heap() в <алгоритм>

Question

Я просто экспериментировал с функцией make_heap() в C++. Ниже приведен код, в котором я отслеживаю элементы, которые сравниваются каждый раз, когда вызывается предикат bool (), путем их печати.

#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,