SE

ヒープソートのもつ性能には、どのようなものがあるでしょうか？

PM

最大値を容易に求められることや消費メモリーが少ないことなどが考えられます。

ヒープソートとは？

ヒープソート（heap sort）は整列データを順序木（木構造の構成）にし、そこから最大値や最小値を取り出して整列していくことを繰り返すアルゴリズムです。ヒープソートを含む整列アルゴリズムは、主に情報処理で使われます。また、ヒープソートと似た用語にヒープ領域がありますが、ヒープ領域とヒープソートは全く無関係のものです。

ヒープとは？

ヒープ（heap）とはデータ構造の一種で、木構造（ツリー構造）のうち親要素が子要素より常に大きいor小さいという条件を満たすものです。ヒープソートは、二分ヒープ（binary heap）という二分木を利用している、比較的に簡単なデータ構造です。

ヒープは二分木として表現

二分木は、二進木またはバイナリツリーとも呼ばれるデータ構造の1つです。根（データ先頭の最大値を持つデータ）が付いた木構造の中で、あるノード（節点）が持つ子の数が高々2のものを指します。典型的には、2つの子はそれぞれ左・右と呼ばれています。二分木の各ノードにデータを保持し、親データが2つの子データよりも大きくなる構造です。つまり、全てのデータ中で二分木の根が必ず存在することになります。

ヒープを構築する操作とは？

ヒープを構築する操作では、データをヒープ構造化して先頭の値を取り消すことを繰り返します。つまり、未整列リストから先頭に来た最大値の要素を取り出し、順にヒープに追加していく作業を、全要素追加し終わるまで繰り返すということです。ヒープに追加する作業をするためには、まず上記のようなデータをヒープ構造化する作業が必要になります。

ヒープソートの流れ6つ

まず二分木の配列をヒープ構造にし、根が最大値になるよう並び替えて、並び替えが完了した根の値を整列済みデータとすることを繰り返していきます。そして、全て整列済みデータになったら終了です。とにかく同じ作業を終了まで繰り返すので難しくありませんが、その流れを大まかにでも知っておくと勉強しやすいでしょう。

流れ1：配列に関するヒープを作る

まず、二分木に格納されている配列をヒープ構造にしていきます。二分木の右側と左側のノードの値を比べて、どちらが最大値になるのかを確認します。そして、最大値によって、適した操作をします。ヒープでは親が子より最大値になるようにしていきます。操作の内容には、値に1や2などを足したり引いたり、他のノードとの比較などがあります。

流れ2：配列の先頭と最後の要素を入れ替える

下から順番に入れ替えていき、根が最大値になるようにしていきます。はじめに一番下の葉と親を比較し、親が大きくなるようにします。次にその1つ上のグループを比較して一番大きな数値を必要なところと入れ替え、さらに上のグループも同じように値を入れ替える、ということを一番上のグループにたどり着くまで繰り返します。

流れ3：配列から最後の要素を消す

最大値になった根を、整列済みデータへ追加します。一番上の根が最大値になりますので、整列済みデータに最大値を追加します。整列済みデータとなった値を除き、再び未整列データで木構成を作ります。この時には、一番下にある最小値を一番上に持っていきます。

流れ4：配列の先頭にmin_heapifyを実行

配列の先頭にmin_heapifyを実行すると、あるノードと配下のノードがヒープの条件を満たすための操作が起きます。あるノードとその子ノードがヒープの条件に該当しないが、子ノードとその配下のノードがヒープの条件に該当する時、条件を満たさないノードたちがヒープの条件を満たすようにノードを交換する操作になります。

流れ5：流れ2～流れ4を繰り返す

上記までの流れを繰り返します。ヒープソートは最大値で追っていくので、最終的に最小値がなくなるまで上記の流れを繰り返すことになります。そのため、1回この流れを覚えてしまえば単純な作業になるので、難しくはないでしょう。ただ、覚えるまでが複雑な印象を持たれるものなので、実際に取り組んでみることが大事です。

流れ6：ヒープ構造が無くなることで終了

上記の流れを繰り返して、ヒープ構造がなくなったら、ヒープソートの作業は終了です。繰り返していくと最後に最小値が残りますので、それを整列済みデータに格納したら終わりということになります。やること自体は単純で簡単とされますが、最大値を求めるにあたり推測が必要になることもあるので、気長に取り組みましょう。

ヒープソートのもつ効果5つ

ヒープソートには特徴となる効果があり、それらはメリットになることもあります。ヒープソートがどのようなものなのか知るのにも役立つ情報なので、以下に5つほどご紹介していきます。ヒープソートについて詳しく知りたい人は、ぜひ参考にしてください。

効果1：最大値を容易に求められる

ヒープソートは、一度構築されると部分的に構造が崩れても再構築が可能で、この性質を利用すればヒープ構造から順に最大値を取り出す作業は比較的に難しくないと言われています。最大値を取り出す作業が他よりも簡単ということは、効率的にソートが行なえることを表しています。時と場合に応じてヒープソートを使用すると良いでしょう。

効果2：整列に関する作業領域が不要

ヒープソートは、配列にある要素を作業領域に追加しなくても、理論上は推測値の計算量を達成できるアルゴリズムだと言われています。配列にある要素を作業領域に追加することが不要というのは、入力の要素数に比例する作業領域を必要としないという意味です。つまり、値の交換を行なうための定数個の作業領域は必要になりますので注意しましょう。

効果3：再帰処理が不要

ヒープソートはあらかじめ決まった回数を繰り返すため、再帰呼び出しを使用せずに計算量のオーダー（オーダリングでメモリーへのアクセス順序を指定）ができます。再帰呼び出しが必要ない時は、メモリーのオーダーがO(1)になります。決まった回数をループ的に処理していくので、簡単かつ速くて効率的な作業になるでしょう。

効果4：品質に関係なく高速なソートが可能

ヒープソートは、並び替えるもともとのデータの品質に関係なく、高速なソートが可能です。これはヒープトリーと呼ばれる特殊な構造の中にデータを格納していくために実現された効果で、その特殊性を利用してソートをしていくことから高速かつ品質に無関係な作業ができると言われています。ただし、並び方などの条件によっては逆に遅くなることもあるので、理解しておきましょう。

効果5：消費メモリーが少ない

ヒープソートは、メモリーの消費が少ないと言われています。これにもヒープトリーにデータを格納することが関係しているとされ、高速かつ効率的で消費が少ない優秀なソートと言われることもあります。

SE

ヒープソートにはさまざまな効果があるのですね。

PM

そうですね。ヒープソートを上手に利用して、作業の効率化を図りましょう！

ヒープソートについての理解を深めよう

ヒープソートは、やや複雑に見えるものですが、実際には比較的に単純で単調な作業を繰り返していくだけで終了するものです。取り組むためには事前勉強が必要になりますが、勉強しながら取り組んでみた方が意外と単純でそこまで難しくないことが分かるでしょう。あまり深く考えず、実際に取り組んでみることが、理解に繋がります。