Почему sort_heap не поместил элементы в порядке, который я ожидал?

Question

Учитывая следующий код:

// range heap example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool Greater(int a, int b)
{
    if (a > b)
    {
        return true;
    } 
    else
    {
        return false;
    }
}

int main () {
    int myints[] = {10,20,30,5,15};
    vector<int> v(myints,myints+5);
    //vector<int>::iterator it;

    make_heap (v.begin(),v.end(), Greater);
    cout << "initial min heap   : " << v.front() << endl;

    pop_heap (v.begin(),v.end(), Greater); v.pop_back();
    cout << "min heap after pop : " << v.front() << endl;

    v.push_back(9); push_heap (v.begin(),v.end(), Greater);
    cout << "min heap after push: " << v.front() << endl;

    sort_heap (v.begin(),v.end());

    cout << "final sorted range :";
    for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];

    cout << endl;

    return 0;
}

почему возвращаемое значение выглядит следующим образом:

initial min heap   : 5
min heap after pop : 10
min heap after push: 9
final sorted range : 10 15 20 30 9 <= why I get this result, I expect 9 10 15 20 30.

Если я вызываю sort_heap (v.begin (), v.end (), Больше), тогда возвращаемое значение будет 30 20 15 10 9.

Вопрос> В этом примере я создаю минимальную кучу.Это причина, по которой я не могу вызвать sort_heap (v.begin (), v.end ())?

спасибо

Answer 1

Вам нужно передать Greater в sort_heap, как и во всех других операциях с кучей.

sort_heap (v.begin(),v.end(), Greater);

Как упоминает @Blastfurnace, std::greater<int>() предпочтительнее, чем определение вашей собственной функции.Помимо фактора элегантности, существует проблема производительности: когда вы передаете функцию по ссылке для неявного преобразования в функтор, она сначала неявно преобразуется в указатель функции, что может привести к менее эффективному выполнению из-за косвенной инструкции перехода.

Answer 2

sort_heap сортирует диапазон только в том случае, если он упорядочен в куче в соответствии с предоставленным компаратором.Поскольку вы использовали Greater в качестве компаратора во всех операциях кучи, у вас нет элементов в порядке кучи в соответствии с компаратором по умолчанию, поэтому sort_heap не гарантированно работает правильно.Обычный алгоритм сортировки должен работать просто отлично.