ヒープソート(ヒープソート)とは | 意味や読み方など丁寧でわかりやすい用語解説

ヒープソートとは、コンピュータサイエンスにおける整列（ソート）アルゴリズムの一種である。与えられたデータを昇順または降順に並べ替えることを目的とし、特にヒープと呼ばれる特殊な木構造を利用する。多くのソートアルゴリズムの中でも、その効率性と安定した性能から実用的な選択肢として広く認識されている。マージソートやクイックソートと同じく、最悪計算時間がO(n log n)と優れており、かつ追加の作業用メモリをほとんど必要としないという特徴を持つ。これは選択ソートを改良したようなアルゴリズムであり、選択ソートが未整列部分から最大値（または最小値）を線形探索で探し出すのに対し、ヒープソートはヒープ構造を用いることでその最大値（または最小値）の取り出しを効率的に行う点が異なる。

ヒープソートの詳細について解説する。このアルゴリズムは、主に「ヒープの構築」と「ソートの実行」という二つのフェーズに分けられる。まず、ヒープとは完全二分木の一種であり、親ノードが子ノードよりも常に大きい（または小さい）という特性を持つデータ構造である。親が子より大きいヒープを最大ヒープ、小さいヒープを最小ヒープと呼ぶ。ヒープソートでは通常、最大ヒープを利用して昇順にソートする。配列としてヒープを表現する場合、インデックスkのノードの親は(k-1)/2、左の子は2k+1、右の子は2k+2のインデックスにそれぞれ位置するという関係が成り立つ。この配列での表現により、木構造をポインタを使わずに効率的に扱うことが可能になる。

最初のフェーズである「ヒープの構築」では、整列されていない与えられた配列を最大ヒープの構造へと変換する。この操作は、配列の末尾から一つずつ親ノードを遡りながら、その部分木がヒープの条件を満たすように調整していくことで行われる。具体的には、あるノードを根とする部分木に対し、そのノードと自身の子ノードを比較し、最大値を持つ子ノードと必要に応じて要素を交換する。もし交換が発生した場合、交換によって移動した子ノードの位置で再び同じ比較と交換の処理を繰り返す。この処理を「ヒープ化（heapify）操作」と呼ぶ。配列の末尾から最初の非葉ノード（つまり、最後の親ノード）から順に根までこのヒープ化操作を適用することで、最終的に配列全体が最大ヒープの条件を満たすように変換される。このヒープ構築にかかる時間はO(n)である。

次のフェーズである「ソートの実行」では、構築された最大ヒープから実際にソート済みの配列を生成していく。最大ヒープの性質上、根（ルート）には常にヒープ内の最大値が格納されている。この最大値を配列の末尾の要素と交換する。交換後、末尾に移動した要素はヒープ内で最も大きな値であるため、ソート済みの領域として確定し、これ以降は操作の対象外となる。ヒープのサイズは一つ減少し、根の位置には新しい要素が来たことでヒープの性質が一時的に壊れる可能性がある。そこで、残りのヒープ（サイズが一つ減ったもの）に対して再度ヒープ化操作を行い、再び根に最大値が来るように調整する。この「最大値の取り出しと末尾との交換」「ヒープサイズの縮小」「ヒープ化操作」という一連の処理を、ヒープのサイズが1になるまで繰り返す。最終的に、配列の末尾から先頭に向かって最大値が順に並べられていき、全体として昇順にソートされた配列が得られる。このソート実行にかかる時間はO(n log n)である。

ヒープソートの特性としては、まずその計算量が挙げられる。ヒープ構築にO(n)、ソート実行にO(n log n)の時間がかかるため、全体の計算時間はO(n log n)となる。この計算量は最悪の場合、平均の場合ともにO(n log n)であり、入力データの状態に左右されにくいという安定性を持つ。これはクイックソートの最悪計算量がO(n^2)となる可能性を考えると大きな利点である。また、追加の作業用メモリをほとんど必要としない「インプレースソート（in-place sort）」である点も特徴だ。これは、ソート対象の配列自体の中でデータの並べ替えを行うため、メモリ効率が非常に良いことを意味する。しかし、ヒープソートにはいくつかの欠点も存在する。一つは「安定ソートではない」という点である。安定ソートとは、同じ値を持つ要素が複数ある場合、それらの相対的な順序がソート後も保たれることを指すが、ヒープソートでは要素の交換によって相対順序が変化する可能性があるため、この条件を満たさない。また、要素のアクセスパターンがランダムになりやすく、CPUのキャッシュ効率があまり良くない場合があるという指摘もある。これにより、理論的な計算量ほど実際の実行速度が出ないケースも存在する。しかし、これらの欠点があったとしても、その堅実な性能と省メモリ性は、多くの場面でヒープソートを有効なソートアルゴリズムとして位置づけている。