heap (ヒープ) は、すべてのノードの値がそれぞれの子に関する値より大きい二分木です。また、ヒープと二分木は、ノード i の子を、位置 2 * i + 1 および 2 * i + 2 に配置することによって、効率よく vector に格納することができます。
この符号化を使用すると、ヒープの最大値は常に初期位置にあるため、極めて効率よく検索することができます。さらに、新規要素をヒープに追加し、最大要素をヒープから削除することができる効率的な対数アルゴリズムもあります。したがって、ヒープは、第 11 章で説明した priority queue データ型の本来の表現です。
デフォルトの演算子は、要素型に固有の小なり演算子 < です。必要に応じて、代替演算子を指定することができます。たとえば、大なり演算子 > を使用することによって、最大要素の代わりに最小要素を最初の位置で検出するヒープを構築することができます。
アルゴリズム make_heap() は、ランダムアクセス反復子で指定された範囲を参照し、それをヒープに変換します。必要なステップ数は、範囲内の要素数の 1 次関数です。
void make_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
新規要素をヒープに追加するには、たとえば vector や deque のメンバー関数 push_back() を使用して要素を範囲の終わりに挿入し、アルゴリズム push_heap() を呼び出します。push_heap() アルゴリズムは、対数演算を 1 回だけ実行して、ヒープ特性を復元します。
void push_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
アルゴリズム pop_heap() は、範囲内の最初と最後の要素を入れ替え、最終要素を使用せずにヒープをコレクションに戻します。したがって、元のコレクションの最大値を範囲の最後の要素として使用することができます。この値は、たとえば vector に back() メンバー関数を使用してアクセスし、pop_back() メンバー関数を使用して削除することができます。同時に、コレクションの残りはヒープ特性を保持します。pop_heap() アルゴリズムは、対数演算を 1 回だけ実行します。
void pop_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
最後に、アルゴリズム sort_heap() がヒープを順序付きまたはソートされたコレクションに変換します。ソートされたコレクションはヒープでもありますが、ヒープはソートされたコレクションではないことに注意してください。
注 : 順序付きコレクションはヒープですが、ヒープは必ずしも順序付きコレクションとは限りません。実際、シーケンスをソートするよりも速く、ヒープをシーケンス内に構築することができます。
ソートは、近似 n log n 演算を使用して実行することができます。この n は、範囲内の要素数を表します。sort_heap() アルゴリズムは安定していません。
void sort_heap (RandomAccessIterator first,
RandomAccessIterator last [, Compare ]);
以下のプログラム例で、これらの関数の使用方法を説明します。
void heap_example ()
// ヒープアルゴリズムの使用方法を説明する
// 完全なソースコードについては alg7.cpp を参照
{
// 15 の乱数を含むヒープを作成する
vector<int> aVec(15);
generate (aVec.begin(), aVec.end(), randomValue);
make_heap (aVec.begin(), aVec.end());
cout << "Largest value " << aVec.front() << endl;
// 最大要素を削除して再ヒープする
pop_heap (aVec.begin(), aVec.end());
aVec.pop_back();
// 97 をヒープに追加する
aVec.push_back (97);
push_heap (aVec.begin(), aVec.end());
// 最後にソートされたコレクションに変換する
sort_heap (aVec.begin(), aVec.end());
}