うさぎでもわかるヒープアルゴリズム

こんにちは、ももやまです！
今回は高速なソートアルゴリズムの1つであるヒープソートのアルゴリズムについて分かりやすくまとめたいと思います！

スポンサードリンク

１．ヒープソートってどんなソートなの？

では、ヒープソートはどのようにしてソートしていくのかについて、手順ごとに図を使って丁寧に説明していきたいと思います。

今回は、 a[8] = {14,9,3,12,21,8,1,17} を昇順（1,2,3…）にソートします。

(1) 手順1　配列を木構造にする

まずは下のように配列を左上から順番に木構造に並べます。

(2) 手順2　木構造をヒープ構造にしていく

つぎに作った配列をヒープ構造にしていきます。
ヒープソートは、後ろから順番にソートするアルゴリズムなため、ヒープ化する際は、昇順ソートの場合はヒープは降順,、降順ソートの場合はヒープは昇順にする必要があるため注意してください。
ヒープ構造とは、すべてのノードにおいて「親ノードは、（子ノードが存在すれば）どの子ノードよりも大きい」という条件を満たした構造を表します。 *1

では、ヒープにしていこうと思います。
ヒープかどうかをチェックする必要があるのは、子ノードが存在する親ノードですね。なので、子ノードがないdata[4]とかdata[5]はチェックの必要がありません。
今回子ノードが存在するのは0番目から3番目ですね。なので、3番目、2番目、1番目、0番目の順番にチェックすればいいです。

まずは、3番目のノードを確認します。子ノードには17がありますね。親と子の順番が逆になってるので、3番目と7番目の要素を交換します。

つぎに2番目のノードを確認します。子ノードには8と1がありますね。
このように子ノードが2つ繋がれている場合は、まず子ノード同士で比較を行います。子ノードのうち、大きいのは8ですね。なので、交換する候補は8のほうになります。
2番目の親ノードは3に対し、子ノードの交換候補は8ですね。子ノードのほうが大きいので、親ノードと交換する候補である8と交換します。

つぎに1番目のノードを確認します。子ノードには17と21がありますね。
大きいのは21なので、21が交換する候補となります。親ノードの9と子ノードの交換候補の21と比べると、21のほうが大きいので交換を行います。*2

最後に0番目（根）を確認します。子ノードには21と8があります。なので交換候補は21です。親ノードは14なので子ノードの交換候補と交換をします。

これで終わり！　と思いますよね。
でもよーく見てください。入れ替えたノード（1番目のノード）とその子（3番目、4番目の子ノード）がよくみたらヒープになっていませんね。
このように入れ替えた相手のノードに子ノードが繋がれている場合、入れ替えた相手のノードがヒープになっているかの確認が必要になります。
今回はヒープになっていないので再びヒープになるように順番を入れ替えます。

入れ替えた先（3番目）にまた子ノード（7番目）が繋がれていますね。なので入れ替えた先のノードとその子ノードがヒープになっているかを確認します。
今回はヒープになっていますね。なので交換の必要がありません。

(3) 先頭（0番目）と一番うしろのノードを交換する

つぎにヒープ構造になったノードの先頭と一番うしろのノードを交換します。
さらに一番後ろのノードはもう使うことがないので木構造から切り離してしまいます。

ヒープ構造のノードの先頭は一番大きいので、先頭と一番うしろを交換することで、後ろの値が一番大きくなり、後ろから降順（10,9,8,7…）ソートができますね。後ろから降順ということは、前から数えると昇順になりますね。

(4) 残ったノードで(2)～(3)を繰り返す

あとは(2)と(3)をソートが終わるまで繰り返すだけです。
繰り返す際には、先頭（0番目）のノード以外はすべてヒープになっているため、先頭の親のノードについてだけヒープの確認を行い、ヒープでなければヒープになおします。
昇順にソートが完了するまでのアニメーションを作ってみたので参考までにどうぞ！

上のアルゴリズムをまとめるとこのようになります

スポンサードリンク

２．ソート速度の計測

ヒープソートの高速ソートが早い！と実感していただくため、実際にソートさせてみました。

• 使用言語はRuby
• データの範囲が1～10,000の場合(a)と1～100,000,000の場合(b)の2つで測定し、データの範囲による差を調べる
• 要素数 \( n \) は10,000からスタートし、2倍ずつにしていく。

気になる測定結果は…!? ついでに選択ソート（オーダー： \( O(n^{2}) \) ）の時間と比較してみました。

さらにグラフ化してみました。 選択ソート部分はグラフには入れていません。

データ数が2倍になると、ソートにかかる時間は2倍ちょいくらいになっていますね。
\( O(n \log n) \) ソートがいかに早いソートかがわかると思います。選択ソートを見てください。ヒープソートなら1秒ちょいでできる要素数320,000のソートを42分かけてやっています。このように高速ソートは要素数が大きくなると爆発的なスピードを発揮します。 要素数1000万でも1分ちょいですよ！！　選択ソートだと何年かかるんでしょうか。

また、ヒープソートはデータ範囲による時間差は見受けられませんね。つまりヒープソートはどのようなデータであっても時間差（ステップ数）はほぼ変わらないアルゴリズムだってこともわかりますね。

スポンサードリンク

３．ソースコード

Rubyでヒープソートを実装してみました。

github.com

４．練習

こちらで練習フォームを用意してみたので期末試験などで「ヒープ化せよ」などの問題が出る人はこちらで練習してみてください！

forms.gle

また、配列を「ヒープ化」したものを木構造で可視化するプログラムも作成してみました！
こちらをご覧ください！

momoyama1192.github.io

５．さいごに

今回はソートアルゴリズムの中でも高速なソートの一種であるヒープソートについてまとめました。
マージソートやクイックソートに比べてはマイナーなソートかもしれませんが、この記事をみてヒープソートのことはたまには思い出してあげてください……。