алгоритм функции make_heap () в & lt; алгоритме & gt;
Я просто экспериментировал с функцией 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
любая помощь ?
Решение
Я бы не сказал, что существует достаточно стандартизированный алгоритм, чтобы можно было ожидать выполнения определенного набора сравнений. Какие является стандартизирована сложность алгоритма, и пока число сравнений имеет линейный порядок, вы должны хорошо идти. Более того, похоже stl с точки зрения количества сравнений работает лучше, чем вы, так что вам не стоит беспокоиться.
Как предлагается в комментариях, вы всегда можете прочитать код реализации std::make_heap что ваш компилятор использует, но нет гарантии, что одна и та же реализация будет использоваться во всех реализациях stl,
Другие решения
Других решений пока нет …