ヒープソート

2025年10月20日

ヒープソート

英語表記: Heapsort

概要

ヒープソートは、データを効率的に並べ替える手法である「ソートアルゴリズム」の一つとして、「アルゴリズムと計算量」という大分類の中で非常に重要な位置を占めています。具体的には、「ヒープ構造」と呼ばれる特殊な二分木を利用し、要素間の大小関係の「比較」に基づいて順序を決定するため、「比較ソート」に分類されます。このアルゴリズムは、データの量 $N$ に対して、最悪の場合でも計算量が $O(N \log N)$ で済むという、非常に安定したパフォーマンスを持つことが大きな特徴です。

詳細解説

ヒープソートの理解には、その名前の由来となっている「ヒープ」というデータ構造を把握することが不可欠です。私たちが学んでいる「アルゴリズムと計算量」の分野において、データ構造の特性を最大限に活用している点が、ヒープソートの魅力的な部分だと思います。

ヒープ構造とは

ヒープとは、配列を用いて実装されることが多い、完全二分木の性質を持つデータ構造です。ヒープには順序付けのルールがあり、これは「ヒープの性質」と呼ばれます。

最大ヒープ: 親ノードの値が、必ずその子ノードの値よりも大きい（または等しい）。この場合、根（ルート）には常に最大値が存在します。
最小ヒープ: 親ノードの値が、必ずその子ノードの値よりも小さい（または等しい）。この場合、根には常に最小値が存在します。

ヒープソートでは、一般的に最大ヒープを利用して昇順ソートを行います。

動作原理：二つのフェーズ

ヒープソートの処理は、データをソート対象の「アルゴリズム」として実行するにあたり、非常に論理的に二つのフェーズに分かれています。

フェーズ1：ヒープの構築（Heapify）

まず、ソート対象の配列全体を論理的にヒープ構造と見立てます。この配列を「ヒープの性質」を満たすように変形させるのが、ヒープの構築フェーズです。

これは、配列の後半部分（二分木の葉ノードがあるあたり）から順に、親ノードと子ノードを比較し、必要に応じて要素を入れ替える（ダウンヒープ操作）ことで行われます。このフェーズが驚くべきことに、要素数 $N$ に対して線形時間に近い $O(N)$ の計算量で完了します。大規模なデータセットでも、準備段階がすぐに終わるのは嬉しいですよね。

フェーズ2：ソートの実行

ヒープが構築されると、最大ヒープの根には、配列全体の最大値が位置しています。この最大値を配列の正しい位置に移動させ、残りの要素で再びヒープを再構築していく作業がソートの実行フェーズです。

最大値の取り出し: 根にある最大値と、配列の末尾の要素を交換します。
ソート済み領域の確保: 交換された末尾の要素は、これでソート済みとして確定し、以降のヒープ操作の対象から除外されます。
再ヒープ化: 交換によってヒープの性質が崩れた根に対し、再びダウンヒープ操作を行い、残りの要素の中で次点の最大値が根にくるように調整します。この調整により、ヒープの高さ（深さ）分、つまり $\log N$ の計算量がかかります。

この「最大値を取り出し、ヒープを再構築する」という操作を、ヒープに残る要素がなくなるまで $N-1$ 回繰り返します。

計算量と分類体系における位置づけ

フェーズ2では、$\log N$ の再ヒープ化操作を $N$ 回繰り返すため、全体の計算量は $O(N \log N)$ となります。

この $O(N \log N)$ という計算量は、「アルゴリズムと計算量」の文脈で非常に優秀です。なぜなら、同じ「比較ソート」に分類されるクイックソートが最悪時に $O(N^2)$ になる可能性があるのに対し、ヒープソートは常にこの安定した性能を保証してくれるからです。計算量の安定性は、特に予測不能なデータが入力されるシステムにおいて、信頼性を高める上で非常に重要視される特性なのです。また、ヒープソートはメモリをほとんど追加で必要としない（インプレース）点も評価されています。

具体例・活用シーン

ヒープソートの動作は、抽象的で分かりにくいと感じるかもしれませんが、その仕組みを理解するための具体的なアナロジーを考えてみましょう。

アナロジー：ピラミッド型の組織での最優秀社員選定

ヒープソートは、巨大な組織の中から「最も優秀な人」を効率的に選抜し、その人が抜けた後も「次点の優秀な人」をすぐに特定できる仕組みに似ています。

構造: 組織図全体が「ヒープ構造」だとイメージしてください。この組織では、上司（親ノード）は必ず部下（子ノード）よりも高い評価を受けているというルール（最大ヒープの性質）があります。
構築フェーズ: まず、全社員をこのルールに従って配置し直します。これにより、ピラミッドの頂点（根）には、組織全体の「最優秀社員」が自動的に位置することになります。
選定（ソート）の実行:
1. 頂点の最優秀社員（最大値）を「殿堂入りリスト」に記録します（配列の末尾へ移動）。
2. 最優秀社員が抜けた穴には、組織の末端にいた社員（配列の端の要素）が一時的に配置されます。
3. しかし、この新しい頂点の社員は必ずしも優秀ではありません。そこで、組織はすぐに再評価を行います。この社員を子ノードと比較し、より優秀な社員が上にくるように順位を入れ替えます。この再評価によって、再び残りの社員の中での「次点の最優秀社員」が頂点に浮かび上がります。

この選定プロセスを繰り返すことで、組織全体の社員が評価の高い順に並んだリストが完成します。ヒープソートは、この「最大値を繰り返し取り出す」という操作を、ヒープという効率的な構造を利用して実現しているのです。

実際の活用シーン

優先度付きキューの実装: ヒープ構造は、処理すべきタスクに優先度がある場合に、常に最も高い優先度のタスクを効率よく取り出すための「優先度付きキュー」として多用されます。ヒープソートは、そのヒープ構造をソートに応用したものです。
大規模データセットのソート: メモリの制約が厳しい環境で、安定した $O(N \log N)$ の性能が必要な場合に、ヒープソートは有力な候補となります。追加メモリがほぼ不要であるため、リソース効率を重視する「アルゴリズムと計算量」の観点から非常に優れています。