EN
JP
KRヒープソートとは？JavaScriptでHeap Sortを実装する方法を解説
ヒープソートは、ヒープと呼ばれるデータ構造を利用して配列を並び替えるソートアルゴリズムです。バブルソート、選択ソート、挿入ソートのような基本的なソートアルゴリズムより効率が良く、最悪ケースでもO(n log n)で動作する点が特徴です。マージソートやクイックソートと同じく高速ソートに分類されますが、ヒープソートは単なる比較や分割だけでなく、木構造の性質を配列上で扱う点に特徴があります。そのため、ソートアルゴリズムだけでなく、データ構造への理解を深めたい人にも重要なテーマです。
JavaScriptでは、実務で配列を並び替える場合、標準のArray.prototype.sort()を使うことがほとんどです。しかし、ヒープソートを学ぶことで、配列を木構造のように扱う方法、最大値を効率よく取り出す仕組み、heapifyによってヒープ条件を保つ処理などを理解できます。特に、親ノードと子ノードのインデックス関係を使って木構造を配列で表現する考え方は、アルゴリズム学習の重要なステップです。本記事では、ヒープソートの基本、ヒープ構造、最大ヒープ、heapify処理、JavaScriptでの実装方法、計算量、メリット・デメリット、学習時のポイントまで分かりやすく解説します。
1. ヒープソートとは？
ヒープソートとは、ヒープというデータ構造の性質を利用してデータを並び替えるソートアルゴリズムです。ヒープは、完全二分木に近い構造を配列で表現できるデータ構造であり、親子関係に特定のルールを持ちます。最大ヒープを使う場合、親ノードの値は子ノードの値以上になります。この性質により、最大ヒープでは最も大きい値が常に根、つまり配列の先頭に置かれます。ヒープソートでは、この最大値を利用して配列を整列させます。
具体的には、まず配列全体を最大ヒープに変換します。その後、先頭にある最大値を配列の末尾と交換し、末尾の値を確定させます。次に、ヒープ対象の範囲を1つ小さくし、残りの要素に対して再びheapifyを行って最大ヒープを保ちます。この処理を繰り返すことで、大きい値から順番に後ろへ確定していき、最終的に配列全体が昇順に整列されます。ヒープソートは、最大値を効率的に取り出す構造を利用したソートだと考えると理解しやすいです。
1.1 ヒープ構造とは？
ヒープ構造は、親子関係を持つ木構造の一種です。ただし、実装では必ずしも明示的なノードオブジェクトを作る必要はなく、配列だけで表現できます。配列のインデックスiにある要素の左の子は2 * i + 1、右の子は2 * i + 2で求められます。また、ある要素の親のインデックスはMath.floor((i - 1) / 2)で求められます。このインデックス関係を使うことで、配列を木構造のように扱えます。
この考え方は、ヒープソートを理解するうえで非常に重要です。たとえば、配列の先頭要素は木の根にあたり、その子はインデックス1と2に存在します。さらに、インデックス1の子は3と4、インデックス2の子は5と6というように、配列上の位置だけで親子関係を計算できます。つまり、ヒープソートでは、配列を単なる横並びのデータとして見るのではなく、親子関係を持つ構造として扱います。この視点が分かると、heapifyの処理も理解しやすくなります。
1.2 最大ヒープとは？
最大ヒープとは、親ノードの値が子ノードの値以上になるように配置されたヒープです。この条件がすべての親子関係で成り立つと、ヒープ全体の最大値は必ず根に置かれます。配列で表現する場合、根はインデックス0なので、最大ヒープではarray[0]が最大値になります。ヒープソートでは、この性質を利用して、最大値を効率よく見つけます。通常の配列で最大値を探すには全体を確認する必要がありますが、最大ヒープなら先頭を見れば最大値が分かります。
昇順に並べたい場合、最大ヒープを作ってから先頭の最大値を末尾へ移動します。末尾に移動した最大値は、もう正しい位置にあるため、以降のヒープ対象から外します。その後、先頭に移動してきた別の値によってヒープ条件が崩れる可能性があるため、再びheapifyを行って最大ヒープに戻します。この処理を繰り返すことで、後ろから順番に大きな値が確定し、最終的に配列全体が昇順になります。
1.3 ヒープソートの特徴
ヒープソートの大きな特徴は、最良ケース、平均ケース、最悪ケースのいずれでもO(n log n)で動作することです。クイックソートのようにピボット選択によって最悪ケースがO(n^2)になるタイプではないため、計算量の安定性があります。また、ヒープソートはインプレースに実装しやすいアルゴリズムです。つまり、元の配列の中で要素を交換しながらソートできるため、追加メモリを抑えやすいという利点があります。
一方で、ヒープソートは基本ソートより実装が複雑です。配列を木構造として扱う考え方、親子インデックスの計算、heapifyによるヒープ条件の修復などを理解する必要があります。また、ヒープソートは基本的に安定ソートではありません。同じ値を持つ要素の元の順序が維持されない可能性があります。そのため、安定性が重要な場合はマージソートや安定性が保証された標準ソートを検討する必要があります。ヒープソートは、効率とデータ構造の理解を深めるための学習価値が高いアルゴリズムです。
2. ヒープソートの動作手順
ヒープソートは、大きく分けて2段階で動作します。最初の段階では、配列全体を最大ヒープに変換します。最大ヒープができると、配列の先頭に最大値が置かれます。次の段階では、その最大値を配列の末尾と交換し、末尾を確定済みとして扱います。その後、ヒープ対象の範囲を1つ小さくし、残りの要素に対してheapifyを行って再び最大ヒープを作ります。この処理を繰り返すことで、配列の後ろから順に値が確定していきます。
ヒープソートの中心となる処理はheapifyです。heapifyとは、あるノードを起点として、ヒープ条件が崩れている場合に親と子を比較し、必要に応じて交換しながら正しいヒープ構造へ戻す処理です。最大ヒープでは、親が子以上でなければなりません。もし子の方が大きければ、親と最大の子を交換します。交換後、さらに下の階層でヒープ条件が崩れている可能性があるため、同じ処理を再帰的または反復的に続けます。このheapifyを理解することが、ヒープソート理解の鍵になります。
2.1 最大ヒープを作る
ヒープソートでは、まず配列全体を最大ヒープに変換します。最大ヒープを作るときは、末端の親ノードから順にheapifyを行います。葉ノードは子を持たないため、heapifyする必要がありません。配列の長さをnとすると、最後の親ノードのインデックスはMath.floor(n / 2) - 1で求められます。この位置から先頭に向かってheapifyを行うことで、配列全体を効率よく最大ヒープへ変換できます。
最大ヒープを作る段階では、まだ配列全体がソートされているわけではありません。あくまで、親が子以上になるというヒープ条件を満たす構造を作っているだけです。最大ヒープになった配列では、先頭に最大値が来ますが、その他の要素が完全に昇順や降順に並んでいるわけではありません。この点を理解しておくことが大切です。ヒープソートは、最大ヒープを作ったあと、最大値を末尾へ移動する処理を繰り返すことで、最終的な並び順を作っていきます。
2.2 最大値を末尾へ移動する
最大ヒープでは、先頭要素が最大値です。昇順に並べたい場合、この最大値は配列の最後に置かれるべき値です。そのため、先頭要素と末尾要素を交換します。交換後、末尾に移動した最大値は正しい位置に確定します。以降の処理では、この末尾要素をヒープ対象から外し、残りの範囲だけを再びヒープとして扱います。このように、ヒープソートでは後ろから順番に値が確定していきます。
ただし、先頭と末尾を交換すると、根に別の値が来るため、最大ヒープの条件が崩れることがあります。そこで、交換後に根からheapifyを行い、残りの範囲を再び最大ヒープへ戻します。これにより、次に大きい値が再び先頭に来ます。そして、その値をまた現在の末尾と交換します。この流れを繰り返すことで、最大値、次に大きい値、その次に大きい値という順番で後ろへ配置されていきます。
2.3 heapifyを繰り返す
heapifyは、ヒープソートの中で何度も使われる重要な処理です。最初に配列全体を最大ヒープにするときにも使われますし、最大値を末尾へ移動した後にヒープを修復するときにも使われます。heapifyでは、現在の親ノード、左の子、右の子を比較し、最も大きい値が親の位置に来るようにします。もし親より子の方が大きければ交換し、その交換先でもヒープ条件が崩れている可能性があるため、さらにheapifyを続けます。
この処理を繰り返すことで、ヒープ対象範囲の中では常に最大値が先頭に来る状態を保てます。ヒープソートは、最大ヒープを作る、最大値を末尾に移動する、heapifyでヒープを修復する、という流れを繰り返すアルゴリズムです。最初は複雑に感じるかもしれませんが、小さな配列で実際に親子関係を確認しながら追うと理解しやすくなります。特に、どのインデックスが親で、どのインデックスが子なのかを意識することが大切です。
3. JavaScriptでヒープソートを実装する
JavaScriptでヒープソートを実装するには、まずheapify関数を作ります。heapifyでは、親ノードと左右の子ノードを比較し、最も大きい値が親の位置に来るようにします。もし子ノードの方が大きければ、親とその子を交換します。交換が発生した場合、交換先の下位部分でヒープ条件が崩れている可能性があるため、さらにheapifyを行います。この処理によって、指定した範囲のヒープ構造を維持できます。
次に、ヒープソート本体では、配列全体を最大ヒープに変換し、その後で最大値を末尾へ移動する処理を繰り返します。この記事では、元の配列を直接変更しないように、最初に[...numbers]でコピーを作っています。学習用としては、元配列を保護しながら処理を確認できるため分かりやすいです。ただし、ヒープソート自体はインプレースに実装できるアルゴリズムであり、元配列を直接変更する形にすれば追加メモリを抑えることもできます。
3.1 heapify関数
heapify関数は、ヒープソートの中心となる処理です。引数として、対象の配列、ヒープとして扱う範囲のサイズ、heapifyを開始する根のインデックスを受け取ります。まず、現在の根を最大値の位置として仮定し、左の子と右の子のインデックスを計算します。左の子がヒープ範囲内にあり、親より大きければ、最大値の位置を左の子に更新します。右の子についても同じように比較します。
左右の子と親を比較した結果、最大値の位置が元の根と異なる場合は、親と最大の子を交換します。交換すると、その子の位置以下でヒープ条件が崩れている可能性があるため、交換先を根として再びheapifyを呼び出します。この再帰処理によって、上から下へヒープ条件を修復できます。heapifyを理解すると、ヒープソート全体が「最大値を先頭に保つ仕組み」であることが見えてきます。
function heapify(array, heapSize, rootIndex) { let largest = rootIndex; const left = 2 * rootIndex + 1; const right = 2 * rootIndex + 2; if (left < heapSize && array[left] > array[largest]) { largest = left; } if (right < heapSize && array[right] > array[largest]) { largest = right; } if (largest !== rootIndex) { [array[rootIndex], array[largest]] = [array[largest], array[rootIndex]]; heapify(array, heapSize, largest); }}
3.2 ヒープソート本体
ヒープソート本体では、まず配列のコピーを作り、配列全体を最大ヒープに変換します。最大ヒープを作るために、最後の親ノードから先頭に向かってheapifyを実行します。Math.floor(n / 2) - 1が最後の親ノードのインデックスです。葉ノードは子を持たないため、heapifyする必要がありません。親ノードだけを下から順にheapifyすることで、効率よく最大ヒープを構築できます。
最大ヒープが完成したら、先頭の最大値を末尾と交換します。末尾に移動した値は確定済みなので、次のheapifyではヒープサイズを1つ小さくします。この処理を配列の先頭に向かって繰り返すことで、後ろから順番に大きな値が確定していきます。最終的に、配列全体は昇順になります。コードだけを見ると少し難しく見えるかもしれませんが、「最大値を先頭から末尾へ送る処理を繰り返している」と考えると理解しやすくなります。
function heapSort(numbers) { const result = [...numbers]; const n = result.length; for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(result, n, i); } for (let i = n - 1; i > 0; i--) { [result[0], result[i]] = [result[i], result[0]]; heapify(result, i, 0); } return result;}console.log(heapSort([5, 3, 8, 1])); // [1, 3, 5, 8]
3.3 降順にする方法
ヒープソートで降順にしたい場合は、最小ヒープを使う方法があります。最小ヒープでは、親ノードの値が子ノードの値以下になるように配置します。この場合、最小値が常に根、つまり配列の先頭に来ます。最小値を末尾へ移動する処理を繰り返すと、小さい値から後ろへ確定していくため、最終的に降順の配列を作れます。ただし、最大ヒープによる昇順ソートよりも説明が少し複雑になるため、学習段階ではまず最大ヒープを使った昇順ソートを理解するのがおすすめです。
実務で降順ソートが必要な場合は、標準のArray.prototype.sort()を使って(a, b) => b - aと書く方が簡単です。ヒープソートの降順実装は、アルゴリズムの理解を深めるための応用として扱うとよいでしょう。最大ヒープと最小ヒープの違いを理解すると、ヒープ構造が単にソートだけでなく、優先度付きキューなどにも応用できることが分かります。まずは最大ヒープで昇順を作る流れを確実に理解し、その後で最小ヒープや降順への応用を考えると理解しやすくなります。
4. ヒープソートの計算量
ヒープソートの時間計算量は、最良ケース、平均ケース、最悪ケースのいずれもO(n log n)です。まず、配列全体を最大ヒープに変換します。その後、最大値を末尾に移動し、残りの範囲に対してheapifyを繰り返します。heapifyはヒープの高さに比例する処理であり、ヒープの高さはlog n程度です。この処理を要素数分繰り返すため、全体としてO(n log n)になります。
ヒープソートは、最悪ケースでも安定した計算量を持つ点が強みです。クイックソートのように、ピボットの選び方によって最悪ケースが大きく悪化するタイプではありません。一方で、マージソートのように安定ソートとして扱いやすいわけではなく、実装もやや難しくなります。計算量、メモリ使用量、安定性、実装難易度を比較しながら学ぶと、ヒープソートの位置づけが分かりやすくなります。
4.1 時間計算量
ヒープソートでは、ヒープの高さがlog n程度になります。heapifyは、親から子へと下方向に進みながらヒープ条件を修復する処理なので、1回あたりの計算量はおおよそO(log n)です。最大値を末尾に移動する処理はn - 1回程度行われ、そのたびにheapifyが呼ばれます。そのため、全体の時間計算量はO(n log n)になります。入力データが整列済みでも逆順でも、基本的な計算量は大きく変わりません。
この安定した時間計算量は、ヒープソートの大きな利点です。バブルソートや選択ソートのようなO(n^2)の基本ソートと比べると、大きなデータに対して効率的です。また、クイックソートのように最悪ケースでO(n^2)になる可能性がない点も特徴です。ただし、実際の速度は実装や環境にも左右されるため、実務では標準sort()を使う方が簡潔で最適化されていることが多いです。ヒープソートは、計算量の安定性を学ぶために非常に有用です。
4.2 空間計算量
ヒープソートは、インプレースに実装できるアルゴリズムです。インプレースとは、元の配列の中で要素を交換しながら処理を行い、追加の大きな配列を作らない実装を指します。この場合、必要な追加メモリは交換用の一時的な領域や再帰呼び出しに関わる部分程度で済みます。そのため、ヒープソートはメモリ効率を重視する場合に有利な性質を持っています。
ただし、この記事の実装では、元の配列を守るためにconst result = [...numbers]でコピーを作っています。そのため、コード全体としてはコピー分の追加メモリを使います。学習用やUI開発では、元配列を変更しない安全な書き方が分かりやすい場合があります。一方、アルゴリズムそのものとしては、元配列を直接変更することで追加メモリを抑えることが可能です。空間計算量を考えるときは、アルゴリズムの性質と、実際のコードの書き方を分けて見ることが大切です。
4.3 安定性
ヒープソートは、基本的に安定ソートではありません。安定ソートとは、同じ値を持つ要素の元の順序を維持するソートです。ヒープソートでは、最大値を先頭から末尾へ移動する過程で要素の交換が何度も発生します。そのため、同じ値を持つ要素の順番が入れ替わる可能性があります。数値だけの配列では気にならないこともありますが、オブジェクト配列を扱う場合には注意が必要です。
たとえば、同じスコアを持つユーザーを元の登録順のまま表示したい場合、安定性が重要になります。このようなケースでは、マージソートのように安定ソートとして実装しやすいアルゴリズムや、安定性が保証された標準ソートを使う方が適しています。ヒープソートは、計算量の安定性やメモリ効率の面で強みがありますが、安定性が必要なデータ表示には向かない場合があります。ソートアルゴリズムを選ぶときは、速さだけでなく、同じ値の扱いも考えることが大切です。
5. ヒープソートを学ぶポイント
ヒープソートを学ぶときは、まず配列で木構造を表現する方法を理解しましょう。ヒープは木構造の一種ですが、JavaScriptで実装するときは配列を使います。インデックスから親子関係を計算できることが分かると、heapifyのコードが読みやすくなります。特に、左の子が2 * i + 1、右の子が2 * i + 2になる関係は、ヒープソートの基礎として押さえておきたいポイントです。
次に、最大ヒープの性質を確認しましょう。最大ヒープでは、親が子以上になるため、最大値が常に先頭に来ます。この性質が、ヒープソートで最大値を効率よく取り出せる理由です。ヒープソートは、基本ソートより実装が難しく感じられるかもしれませんが、配列と木構造の関係、最大ヒープ、heapifyの3つに分けて学ぶと理解しやすくなります。小さな配列を使って、各ステップでどの値が交換されるのかを確認するとよいでしょう。
5.1 配列と木構造の関係を理解する
ヒープは木構造ですが、実装では配列を使います。配列のインデックスを使って親子関係を計算できるため、ノードクラスやリンク構造を作らなくても木のような処理が可能です。インデックスiの左の子は2 * i + 1、右の子は2 * i + 2です。この関係を覚えると、heapify関数の中でなぜ左と右の子をそのように計算しているのかが分かります。
配列を木構造として見ることに慣れると、ヒープソートだけでなく、優先度付きキューなどのデータ構造も理解しやすくなります。最初は、配列[8, 5, 3, 1]のような小さな例を使い、インデックス0を根、インデックス1と2を子、インデックス3と4をさらに子として図に描くとよいでしょう。配列上の位置と木構造の位置が対応していることを確認できれば、ヒープソートの処理がより具体的に見えてきます。
5.2 heapifyを重点的に理解する
ヒープソートの難しさは、heapifyにあります。heapifyは、親と左右の子を比較し、最大ヒープの条件が崩れている場合に交換して、下方向へ修復していく処理です。親がすでに左右の子以上であれば、何もする必要はありません。しかし、子の方が大きい場合は、最も大きい子と親を交換します。その交換先でもヒープ条件が崩れている可能性があるため、さらにheapifyを続けます。
heapifyを理解するには、小さな配列で手順を追うのが効果的です。たとえば、親、左の子、右の子の3つだけを見て、どれが最も大きいかを確認します。最大の値が親でなければ交換し、交換後の位置でも同じ確認を行います。この流れを繰り返すことで、部分的に崩れたヒープを正しい最大ヒープへ戻せます。heapifyが分かると、ヒープソート全体の動作が一気に理解しやすくなります。
5.3 他の高速ソートと比較する
ヒープソートは、マージソートやクイックソートと同じく高速ソートに分類されます。ただし、それぞれ特徴が異なります。マージソートは最悪ケースでもO(n log n)で安定ソートとして実装しやすいですが、追加メモリを使いやすいです。クイックソートは平均的に高速ですが、ピボット選択が悪いと最悪ケースでO(n^2)になる可能性があります。ヒープソートは最悪ケースでもO(n log n)で、インプレースに実装しやすい一方、安定ソートではありません。
このように比較すると、ソートアルゴリズムには単純な優劣だけでなく、用途による向き不向きがあることが分かります。安定性を重視するならマージソート、平均的な速度を重視するならクイックソート、最悪ケースの安定した計算量とメモリ効率を意識するならヒープソートというように、それぞれの特徴を整理できます。JavaScriptの実務では標準sort()を使うことが多いですが、これらの違いを理解しておくと、アルゴリズム全体への理解が深まります。
おわりに
ヒープソートは、ヒープ構造を利用して配列を並び替えるソートアルゴリズムです。最大ヒープを作り、最大値を末尾へ移動しながら整列していくことで、昇順ソートを実現します。配列を木構造のように扱い、親子関係をインデックスで計算する点が特徴であり、ソートだけでなくデータ構造の理解にもつながります。
時間計算量は最良ケース、平均ケース、最悪ケースのいずれもO(n log n)であり、最悪ケースでも安定した性能を持ちます。一方で、実装はやや複雑で、基本的には安定ソートではありません。JavaScriptでヒープソートを学ぶことで、heapify、最大ヒープ、配列による木構造表現など、アルゴリズム学習を一段進めるための重要な考え方を身につけられます。
