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 に答える