1

给定以下代码：

// 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()) 的原因吗？

谢谢你

4

2 回答 2

3

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

于 2011-01-24T05:03:32.417 回答
3

您需要像所有其他堆操作一样传递Greater给。sort_heap

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

正如@Blastfurnace 所提到的，std::greater<int>()比定义自己的功能更可取。除了优雅因素之外，还有一个性能问题：当您通过引用传递函数以进行隐式转换到仿函数时，它首先被隐式转换为函数指针，由于间接分支指令，这可能导致执行效率降低。

于 2011-01-24T06:01:38.350 回答