c++ - 为什么 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(), Greater)，则返回值为 30 20 15 10 9。

问题 > 在此示例中，我创建了一个最小堆。这是我不能调用 sort_heap(v.begin(), v.end()) 的原因吗？

谢谢

Answer 1

sort_heap 仅根据提供的比较器对堆排序的范围进行排序。由于您在所有堆操作中都使用 Greater 作为比较器，因此您没有根据默认比较器按堆顺序排列的元素，因此不能保证 sort_heap 正常工作。不过，常规排序算法应该可以正常工作。