C++ STLのヒープ操作徹底解説：make_heap・push_heap・pop_heap・sort_heap・is_heapの使い方

C++ STLには、ヒープ（heap）データ構造を扱うための便利な関数群が用意されています。ヒープを利用すると要素を高速に挿入でき、取り出し操作では常に残りの要素の中で最大の値が得られます。最大値以外の要素の並び順は実装に依存します。本記事では、STLが提供する主要なヒープ操作関数を、サンプルコードと実行結果とともにわかりやすく解説します。

make_heap() ― 範囲をヒープ化する

make_heap() は、コンテナ内の指定した範囲をヒープ構造に変換する関数です。また、front() を使うことで、ヒープの先頭要素（最大値）を参照できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;
}

実行結果

Top element is : 53

push_heap() と pop_heap() ― 要素の挿入と削除

push_heap() は、新しい要素をコンテナに追加した後（push_back後）に呼び出すことで、ヒープの性質を保ったまま再構成します。ヒープのサイズは1増加し、新しく追加された要素は適切な位置へ自動的に配置されます。

pop_heap() は、ヒープの最大要素を末尾へ移動した後（pop_back前）に呼び出すことで、残りの要素を再度ヒープ化します。ヒープのサイズは1減少し、削除後もヒープの性質が維持されます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());
    cout << "Top element is : " << heap.front() << endl;

    // 要素を挿入してヒープを再構成
    heap.push_back(60);
    push_heap(heap.begin(), heap.end());
    cout << "Top element after insert : " << heap.front() << endl;

    // 最大要素を削除してヒープを再構成
    pop_heap(heap.begin(), heap.end());
    heap.pop_back();
    cout << "Top element after deletion : " << heap.front() << endl;
}

実行結果

Top element is : 53
Top element after insert : 60
Top element after deletion : 53

sort_heap() ― ヒープソートによる昇順ソート

sort_heap() は、ヒープソートの手法を用いて、ヒープ内の要素を昇順に並べ替える関数です。ソート後の範囲はもはやヒープではなくなる点に注意してください。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};
    make_heap(heap.begin(), heap.end());

    cout << "Before Sort : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }

    sort_heap(heap.begin(), heap.end());

    cout << "\nAfter Sort : ";
    for (const auto &i : heap) {
        cout << i << ' ';
    }
}

実行結果

Before Sort : 53 43 33 38 28
After Sort : 28 33 38 43 53

is_heap() と is_heap_until() ― ヒープの判定

is_heap() は、指定した範囲がヒープとして成立しているかどうかを判定します。範囲がヒープであれば true を、そうでなければ false を返します。多くの実装では、降順にソートされたコンテナもヒープとして扱われます。

is_heap_until() は、範囲の先頭からどこまでがヒープとして成立しているかを調べ、その境界位置を指すイテレータを返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> heap = {33, 43, 53, 38, 28};

    // ヒープ化前の判定
    if (is_heap(heap.begin(), heap.end()))
        cout << "This is a heap" << endl;
    else
        cout << "This is not a heap" << endl;

    // ヒープ化
    make_heap(heap.begin(), heap.end());

    // ヒープ化後の判定
    if (is_heap(heap.begin(), heap.end()))
        cout << "This is a heap" << endl;
    else
        cout << "This is not a heap" << endl;

    // ヒープとして成立している範囲の終端を取得
    auto iter2 = is_heap_until(heap.begin(), heap.end());
    cout << "The heap elements are : ";
    for (auto iter = heap.begin(); iter != iter2; ++iter)
        cout << *iter << " ";
}

実行結果

This is not a heap
This is a heap
The heap elements are : 53 43 33 38 28

まとめ

C++ STLのヒープ関連関数を使いこなせば、優先度付きキューのような「常に最大値へ高速アクセスしたい」場面を効率的に実装できます。make_heap で範囲をヒープ化し、push_heap／pop_heap で挿入・削除を管理し、sort_heap で整列、is_heap／is_heap_until で状態検証という流れを押さえておきましょう。