为什么sort_heap没有按照我预期的顺序放置元素？

考虑下面的代码：为什么sort_heap没有按照我预期的顺序放置元素？

// 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（））的原因吗？

感谢你只

来源

2011-01-24 q0987

这不是你的问题，但`Greater（）`可以实现为`return a> b;` – 2011-01-24 05:05:35

sort_heap如果是堆排序根据所提供的比较排序范围。由于您在所有堆操作中使用了Greater作为比较器，因此根据默认比较器没有按堆顺序排列的元素，因此sort_heap无法保证正常工作。但是，常规排序算法应该可以很好地工作。

来源

2011-01-24 05:03:32 templatetypedef

与所有其他堆操作一样，您需要将Greater更改为sort_heap。

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

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

来源

2011-01-24 06:01:38 Potatoswatter

为什么sort_heap没有按照我预期的顺序放置元素？

回答

相关问题