C++ で STL ヒープアルゴリズムを使用する

C++ STL のヒープアルゴリズムを使うと、std::vector の範囲を最大ヒープにしたり、その範囲をソートしたり、最大値を末尾へ移動したりできます。std::pop_heap は値を移動するだけです。vector から削除するには、別途消去してください。

std::make_heap 関数で範囲をヒープに変換する

ヒープとは、親子間の規則を満たすように並べられた範囲です。デフォルトの比較では、std::make_heap は最大ヒープを作ります。各親の値は子の値以上となるため、最大値が先頭に置かれます。vector を使った二分ヒープでは、インデックス i の要素の子は、範囲内に位置がある場合、それぞれ 2 * i + 1 と 2 * i + 2 にあります。最小ヒープを作るには、たとえば std::greater<int> のような別の比較を使います。

std::make_heap はヒープの性質を満たすように要素を並べ替えますが、範囲全体をソートするわけではありません。同じ性質を満たす並び方は複数あるため、呼び出し後の特定の値の並びではなく、先頭の値と親子間の比較に基づいてコードを書いてください。

次の単体で実行できる例では、ヒープを作成し、親子間の規則を確認します。正常に実行され、観測された出力を以下に示します。出力ブロック内のラベルは、変更できない例の一部として英語のままです。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

先頭の要素がヒープのトップ値です。vector 内の残りの並びはヒープの性質によってのみ制約されるため、昇順または降順のリストとして扱わないでください。

std::sort_heap 関数でヒープ範囲をソートする

すでにヒープの性質を満たしている範囲に std::sort_heap を呼び出します。デフォルトの比較では、範囲を昇順に並べ替えます。ソート後の範囲はヒープの性質を満たさなくなるため、範囲全体にヒープ操作を行う前に、もう一度 std::make_heap を呼び出してください。

たとえば、std::make_heap(values.begin(), values.end()) の後に std::sort_heap(values.begin(), values.end()) を呼び出すと、同じ範囲をソートできます。デフォルトの比較では昇順になります。

比較関数を受け取るオーバーロードでは、順序を定義する関数または関数オブジェクトを指定できます。ヒープの作成時とソート時には同じ比較を使ってください。たとえば、std::greater<int> で作成したヒープは、ソート時にも同じ比較を指定する必要があります。昇順の結果が目的なら、デフォルトのオーバーロードを使えます。

std::pop_heap 関数でヒープの次の要素を取り出す

std::pop_heap はトップ値を範囲の末尾へ移動し、その前の範囲のヒープの性質を保ちます。vector のサイズは変わりません。その値をコンテナから削除するには、std::pop_heap の後に pop_back() を呼び出します。

要素を追加するには、vector に追加してから std::push_heap を呼び出します。追加した要素より前の範囲は、あらかじめヒープになっている必要があります。std::push_heap は拡張された範囲全体でヒープの性質を回復します。どちらのアルゴリズムでも、ヒープを定義するものと同じ比較を使ってください。

次の単体で実行できる例では、移動したトップ値を確認して別途消去し、その後ヒープの性質を保ちながら値を追加します。正常に実行され、観測された出力を以下に示します。出力ブロック内のラベルは、変更できない例の一部として英語のままです。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

std::pop_heap の後は、最後の要素より前の範囲が再利用できるヒープです。pop_back() で末尾の値を削除すると、vector 全体がそのヒープ範囲になります。この性質を保たずに要素を追加すると、std::push_heap の事前条件を満たしません。