次の方法で共有

sort_heap

  • [アーティクル]

並べ替えられた範囲にヒープを変換します。

template<class RandomAccessIterator>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
   );
template<class RandomAccessIterator, class Predicate>
   void sort_heap(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last,
      Predicate _Comp
   );

パラメーター

  • _First
    ターゲット ヒープ内の最初の要素の位置を示すランダム アクセス反復子。

  • _Last
    ターゲット ヒープの最後の要素 1 を超える位置を示すランダム アクセス反復子。

  • _Comp
    要素が別の値より小さいかを意味を定義するユーザー定義の述語関数オブジェクト。バイナリ述語が満たされなかった場合に完了したら 2 個の引数を受け取り、true と false を返します。

解説

ヒープに 2 個のプロパティがあります:

  • 最初の要素は常に最大値になります。

  • 要素は、対数の時刻に追加または削除される場合があります。

アプリケーションの後にこのアルゴリズムが、スコープに適用する場合は、ヒープはありません。

これは同等の要素の相対位置ディレクティブが必ずしも維持されないため、安定した並べ替えではありません。

ヒープが優先キューを実行するのに最適な方法で、標準テンプレート ライブラリのコンテナーのアダプター priority_queue のクラスの実装で使用されます。

参照される範囲が有効である必要があります; すべてのポインターが dereferenceable なり、シーケンス内で最後の位置は incrementation によって最初からアクセスできます。

複雑度が最大 N の ログ N、N = である (_Last – の _First)。

使用例

// alg_sort_heap.cpp
// compile with: /EHsc
#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>
using namespace std;

void print(const string& s, const vector<int>& v) {
    cout << s << ": ( ";

    for (auto i = v.begin(); i != v.end(); ++i) {
        cout << *i << " ";
    }

    cout << ")" << endl;
}

int main() {
    vector<int> v;
    for (int i = 1; i <= 9; ++i) {
        v.push_back(i);
    }
    print("Initially", v);

    random_shuffle(v.begin(), v.end());
    print("After random_shuffle", v);

    make_heap(v.begin(), v.end());
    print("     After make_heap", v);

    sort_heap(v.begin(), v.end());
    print("     After sort_heap", v);

    random_shuffle(v.begin(), v.end());
    print("             After random_shuffle", v);

    make_heap(v.begin(), v.end(), greater<int>());
    print("After make_heap with greater<int>", v);

    sort_heap(v.begin(), v.end(), greater<int>());
    print("After sort_heap with greater<int>", v);
}

出力例

Initially: ( 1 2 3 4 5 6 7 8 9 )
After random_shuffle: ( 9 2 7 3 1 6 8 4 5 )
     After make_heap: ( 9 5 8 4 1 6 7 2 3 )
     After sort_heap: ( 1 2 3 4 5 6 7 8 9 )
             After random_shuffle: ( 5 8 3 1 2 9 7 6 4 )
After make_heap with greater<int>: ( 1 2 3 4 5 9 7 6 8 )
After sort_heap with greater<int>: ( 9 8 7 6 5 4 3 2 1 )

必要条件

ヘッダー: <algorithm>

名前空間: std

参照

関連項目

heap

標準テンプレート ライブラリ