爲什麼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沒有按照我預期的順序放置元素？

回答

相關問題