プログラミングやアルゴリズムを学ぶ中で「ヒープソート」という言葉に出会う方も多いのではないでしょうか。
「名前は聞いたことあるけど、どんな仕組みなの？」と疑問に思っている方もいるでしょう。
この記事では、ヒープソートとは何か、そのアルゴリズムの仕組みについて、計算量・時間複雑度・データ構造との関係まで、初心者にもわかりやすく解説しています。
ソートアルゴリズムの理解を深めたい方はぜひ最後までご確認ください。
ヒープソートとは？ソートアルゴリズムとしての基本的な意味
それではまず、ヒープソートの基本的な意味と特徴について解説していきます。
ヒープソートとは、「ヒープ（Heap）」というデータ構造を利用した比較ベースのソートアルゴリズムのことです。
ヒープソートは1964年にJ.W.J. Williamsによって考案されたアルゴリズムで、現在でも広く使われている効率的なソート手法のひとつです。
クイックソートやマージソートとともに「O(n log n)」の計算量を持つ代表的なソートアルゴリズムとして知られています。
ヒープソートの主な特徴：時間計算量が最悪でもO(n log n)を保証する・追加メモリをほとんど必要としない（O(1)の空間計算量）・不安定ソートである（同じ値の要素の順序が保証されない）・インプレース（元の配列上で操作する）ソートである。
ヒープデータ構造の基本
ヒープソートを理解するためには、まず「ヒープ」というデータ構造を理解する必要があります。
ヒープとは完全二分木の構造を持ち、親ノードが常に子ノード以上（最大ヒープ）または以下（最小ヒープ）の値を持つという条件（ヒープ条件）を満たすデータ構造です。
ヒープソートでは主に最大ヒープを使い、最大値を効率よく取り出す操作を繰り返すことでデータを整列します。
最大ヒープと最小ヒープの違い
最大ヒープは根（ルート）ノードが最大値を持つヒープであり、最小ヒープは根ノードが最小値を持つヒープです。
昇順ソートには最大ヒープを使い、根の最大値を末尾に移動する操作を繰り返すことで小さい順に並べていきます。
ヒープソートのアルゴリズムの仕組みを詳しく解説
続いては、ヒープソートのアルゴリズムの仕組みを詳しく確認していきます。
ヒープソートは大きく分けて「ヒープ構築フェーズ」と「ソートフェーズ」の2段階で動作します。
フェーズ1：ヒープの構築（Heapify）
まず、ソート対象の配列を最大ヒープに変換します。
これを「ヒープ構築（Build Heap）」と呼び、配列の後ろ半分から順に「下向き調整（Sift Down）」という操作を行うことで実現します。
ヒープ構築の手順（配列 [3, 1, 4, 1, 5, 9, 2] の場合）：
1. 配列を完全二分木として見立てる
2. 最後の親ノードから順に下向き調整（Sift Down）を行う
3. 全ての親ノードの調整が完了すると最大ヒープが完成
結果：[9, 5, 4, 1, 1, 3, 2]（根が最大値9になっている）
フェーズ2：ソートの実行
ヒープが構築できたら、根（最大値）を配列の末尾と交換し、ヒープのサイズを1減らして再びヒープ条件を回復させる操作を繰り返します。
この操作をn-1回繰り返すことで、配列が昇順にソートされます。
ソートフェーズのステップ：
1. 根（最大値）と末尾要素を交換する
2. ヒープのサイズを1減らす（末尾の確定要素を除外）
3. 根から下向き調整（Sift Down）でヒープ条件を回復する
4. ヒープサイズが1になるまで繰り返す
下向き調整（Sift Down）の仕組み
下向き調整とは、ある要素が子ノードより小さくなった場合に、子ノードの大きい方と交換しながら適切な位置まで降ろしていく操作です。
この操作の計算量は木の高さに比例するO(log n)であり、これがヒープソート全体のO(n log n)という計算量の基礎となっています。
ヒープソートの計算量と他のソートアルゴリズムとの比較
続いては、ヒープソートの計算量と他のソートアルゴリズムとの比較を確認していきます。
| アルゴリズム | 最悪計算量 | 平均計算量 | 空間計算量 | 安定性 |
|---|---|---|---|---|
| ヒープソート | O(n log n) | O(n log n) | O(1) | 不安定 |
| クイックソート | O(n²) | O(n log n) | O(log n) | 不安定 |
| マージソート | O(n log n) | O(n log n) | O(n) | 安定 |
| バブルソート | O(n²) | O(n²) | O(1) | 安定 |
ヒープソートの強みと弱み
ヒープソートの最大の強みは、最悪計算量でもO(n log n)を保証する点です。
クイックソートは平均的には高速ですが、最悪ケースでO(n²)になるのに対し、ヒープソートはどんなデータ並びでも安定してO(n log n)で処理できます。
一方、キャッシュの局所性が低いためクイックソートよりも実際の実行速度が遅くなることが多く、実用的な場面ではクイックソートやマージソートが選ばれることが多いでしょう。
まとめ
この記事では、ヒープソートとは何か、そのアルゴリズムの仕組みについてヒープ構築・ソートフェーズ・計算量の比較まで詳しく解説しました。
ヒープソートは最悪計算量O(n log n)・追加メモリO(1)という優れた特性を持つアルゴリズムであり、ソートの基礎を学ぶ上で重要な知識です。
アルゴリズムの仕組みを理解することで、状況に応じた適切なソート手法の選択ができるようになるでしょう。
今回の内容を参考に、ソートアルゴリズムの理解をさらに深めていきましょう。
