【図解】ヒープソート:アルゴリズム【C言語】

本記事では、基本的なソートの一種である「ヒープソート」のアルゴリズム解説・C言語による実装を確認していきます。

 

アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています

図を多く挿入しているため、ページとしては結構長めです。

 

ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。

 

 

 本記事でわかること

  • ヒープソートの基本的な情報
  • アルゴリズムの流れ
  • C言語による実装方法

 

 

こちらの記事で、他のソートアルゴリズムをまとめています。

>>ソートアルゴリズム 計算量・特徴一覧

 

 

アルゴリズム入門書はこの一冊で十分!

 

 

 

 

ヒープソートとは

ヒープソートは、ソートアルゴリズムの一種であり、ヒープ構造を利用したソートです。

 

ちなみに、ヒープは「優先度付きキュー」などと呼ばれることもあります。

 

ヒープソートの基本的な情報は以下のようになります。

 

最悪計算時間 \(O\) 安定性
\(O(nlog(n))\) 安定ではない

 

ヒープソートの計算時間は、\(O(nlog(n))\)であるため、ソートの中では高速に動作する部類です。

 

では、次の章から、実際のヒープソートのアルゴリズムを見ていきましょう。

 

スポンサーリンク

 

ヒープソートのアルゴリズム

ヒープソートのアルゴリズムをわかりやすく説明するために、以下のように、順を追って解説を進めていきます。

 

  1. そもそもヒープとは
  2. ヒープソートアルゴリズムの全体的な流れ
  3. ヒープソートアルゴリズムの具体的な動き

 

1では、ヒープの説明をします。

2では、1の説明をもとに、ザックリとしたヒープソート全体の流れを確認します。

3では、2で確認した動きをどのように実現するのかを確認・解説します。

 

では、さっそく見ていきましょう!

 

 

そもそもヒープとは

ヒープは、データ構造の一種であり、普通の配列を二分木として扱うための構造です。

 

二分木はポインタを使用して実装することが一般的ですが、普通の配列を使用して実装することで、アクセス時間が短縮できるという利点があります。

 

 

具体例を出すと、サイズが10の配列は、以下のように二分木として扱います。

 

 

画像からわかるように、配列の先頭がルートとなり、添え字が1, 2の要素は深さ1のノード、添え字が3,4,5,6の要素は深さ2のノード、、、といった具合です。

 

基本的には左詰めで考えます。

 

何か特別な操作をしたというよりは、「横一列の配列を、こんな感じの二分木として扱いますよ」という、ただそれだけのことです。

 

 

まだ、しっくりこないかもしれないので、別の配列を見てみます。

 

今度は、以下のような配列でヒープを考えてみます。

 

 

ヒープは、形式的に配列の見方を変えるだけなので、以下のような二分木として扱うことになります。

 

 

以上がヒープの説明です。

 

 

ヒープソートでは、最大ヒープという並び方を利用するので、こちらの説明もしておきます。

最大ヒープは、上の説明に毛が生えたような話なので、気楽に読んでください。

 

上で確認した配列は、特に規則のない並び方でした。

最大ヒープでは、二分木として見た場合に、ある条件を満たすように配列を並び替えます

 

その条件は、すべてのノードにおいて「親」>「子」の関係が成り立つ、というものです。

 

こちらも具体例を見てみましょう。

 

例えば、さきほど上で確認した配列を最大ヒープに並び替えると、以下のようになります。

※最大ヒープは一通りだけではないです。

 

 

配列として見た場合は、特に規則があるようには見えませんね。

しかし、これを二分木として見た場合は、以下のようになります。

 

 

この二分木は、自分より上にある要素が、自分よりも大きな値になっていますね。

つまり、「親」>「子」を満たしているということです。

 

これが最大ヒープです。

 

 

ちなみに、最小ヒープというものもありますが、これは最大ヒープの逆だと思ってもらえればOKです。

すべてのノードで「親」<「子」の関係が成立している、ということですね。

今回は出てこないのですが、一応セットで覚えておきましょう。

 

 

これで、最大(最小)ヒープの説明まで終わりました。

 

では、最大ヒープの構造を踏まえた上で、これをどのように利用するのかを見ていきましょう。

 

 

ヒープソートアルゴリズムの全体的な流れ

ここでは、具体的な処理を確認する前に、ザックリとソートの手順を図で確認していきます。

 

さきほど、最大ヒープを確認しましたね。

ヒープソートでは、この最大ヒープをうまく利用することで、配列全体をソートします

 

これは、言葉で説明するよりも図を見た方がわかりやすいので、さっそく図へ移りましょう。

 

 

今回は、具体例として、サイズ8の配列をソートすることにします。

 

 

まずは、この配列をヒープ構造として見ます。

再度確認しますが、これは形式的に見方を変えただけです。

 

 

これを最大ヒープに並び替えてみましょう。

どのように最大ヒープに並び替えるのかは、後ろの方で説明します。

 

 

最大ヒープに並び替えることで、嬉しいことが1つあります。

 

それは、「必ずヒープのてっぺんに最大値が来る」という点です。

ヒープのてっぺんは、配列の先頭なので、最大値を取得するまでの計算時間は\(O(1)\) で済みます。

 

これが、ヒープソートが高速に動作する理由の1つです。

 

では、次に、配列の先頭に移動してきた最大値を、ヒープの末尾と取り換えます。

 

 

この時、配列は以下のように変化しています。

 

 

これは、配列中の最大値が一番後ろに移動した、ということです。

 

今度は、ヒープサイズを1つ減らして、再び最大ヒープに並び替えます。

「ヒープサイズを1つ減らす」、というのは、単純に配列の末尾を無いものとして扱うということです。

 

 

これは、もともとの配列における最大値の次に大きな値が、配列の先頭に移動していることになります。

今回、配列中の最大値「9」は、ヒープに含んでいないため、その次に大きな「8」がヒープのてっぺんに来ている、ということです。

 

では、同様にして、先頭とヒープの末尾を入れ替えます。

このとき、「9」はヒープから除外して考えているため、ヒープの末尾は「1」になります。

 

 

配列はこのように変化します。

 

 

ここまで見ると察しがつくかと思いますが、あとはこれを繰り返すだけで、配列の後ろから順番に大きな値が並んでいきます。

 

イメージとしては、木のてっぺんにあるヒープの最大値を、ひたすら配列の奥へと詰め込んでいく感じです。

 

念のため、もう1セット確認します。

 

まずは、ヒープのサイズを1つ減らします。

つまり、今度は「8」と「9」を無いものとして扱う、ということです。

 

そして、再び最大ヒープに並び替えます。

 

 

次に、ヒープの末尾と先頭を入れ替えます。

今回は、「8」と「9」をヒープに含んでいないため、ヒープの末尾は「3」になりますね。

 

 

配列はこのようになります。

 

 

ここまでの処理を繰り返すことで、配列の後ろから順番にソートが完了します。

 

 

配列の中で、ヒープに含まれない部分だけに着目すると、こんな感じでソートが進みます。

本来は、この空白部分で、何度も最大ヒープへの並び替えが行われています。

 

 

 

ソートの全体的な流れを確認することができたので、残りは具体的なアルゴリズムを確認するだけです。

 

いよいよ終盤なので、最後まで頑張りましょう!

 

 

ヒープソートアルゴリズムの具体的な動き

ヒープソートの流れを再度確認します。

 

  1. 最大ヒープに並び替える
  2. ヒープの先頭と、ヒープの末尾を入れ替える
  3. ヒープサイズを1つ減らす
  4. ヒープサイズが2つ以上であれば①へ戻る

 

ヒープソートの流れはすでに確認済みであるため、ここでは、「いかにして最大ヒープへと並び替えるのか」を解説します。

最大ヒープへ並び替える方法さえわかれば、あとは上で確認した処理を繰り返すだけでソートできますね。

 

 

では、最大ヒープへの並べ替え方を解説していきます。

 

最大ヒープは、すべてのノードにおいて「親」>「子」が成立すればいいわけでしたね。

なので、ここは単純に、「親」<「子」となっている部分を入れ替えていけばよさそうです。

 

 

図で見てみましょう。

 

最初のヒープをこうだとします。

 

 

「親」<「子」となっている部分がいくつかありますね。

では、その部分を入れ替えていきましょう、と言いたいところですが、一体どこから手を付けるべきでしょうか。

 

これは、二分木の下側から入れ替えていく、が正解になります。

 

上からでもできないことは無いのですが、かなり効率が悪くなります

気になる方は、下側から手を付けるパターンを確認したあとに、同様の処理を上からやってみてください。

 

 

では、下側かつ子を持つ親から順番に、以下の処理を行います。

これは、親の視点から見た処理の説明です。

 

  1. 左右の子と自分(親)の値を比較
  2. 自分(親)よりも子が大きい場合は交換
  3. 交換後にも子を持つのであれば、①へ戻る

 

まずは、下側から順番に、子を持つ親を探していきます。

「下側から順番に」は、黄色の矢印と逆の順番のことです。

 

つまり、上の図で言うと、「6」→「9」→「3」→「7」→ 、、、といった具合です。

その中で、最初に子を持つ親を決定します。

 

最初に着目する値は、「1」になりますね。

 

 

次に、親と子を比較します。

今回の例だと、「1」「6」の比較です。

 

このとき、「親」<「子」であれば、それらを交換します。

 

では、交換しましょう。

 

 

交換後、着目していた値「1」は子を持たないので、これで1つの処理が終了です。

 

着目する値を変更して、同様の処理を繰り返します。

次に着目する親は、「8」です。

 

 

では、親と子を比較しましょう。

 

今回は、親の「8」と、子の「3」「9」の比較を行います。

この中で、親より大きい値は「9」なので、それらを交換します。

 

 

交換後、着目していた親「8」は子を持たないので、ここで1つの処理が終了です。

 

再び着目する親を変更します。

次に着目する親は「2」です。

 

 

次は、親の「2」と、子の「6」「7」を比較します。

今回は、左右両方の子が親よりも大きい値ですね。

 

この場合は、その中でも大きな方と交換します

つまり、「2」「7」を交換するということです。

 

 

交換後、着目していた親「2」は子を持たないので、ここで1つの処理が終了です。

 

再び着目する親を変更します。

最後に着目する親は「4」です。

 

 

「4」と、子「7」「9」を比較します。

今回もまた、左右両方の子が親よりも大きな値です。

この場合は、「4」「9」を交換するんでしたね。

 

 

今まで見てきた場合と違って、交換後に、着目している親「4」は子を持っています。

 

なので、再び親と子の比較をします。

 

 

今度は、着目していた親「4」は子を持たないので、これで終了です。

 

また、着目する値も一番上前まで来たので、すべての処理がおしまいになります。

 

確認してみると、これは、すべてのノードにおいて「親」>「子」の関係が成り立っていますね

ここまでが、最大ヒープへの並べ替え方です。

 

次の章では、これをC言語で実装していきます。

実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。

 

スポンサーリンク

 

ヒープソートの実装【C言語】

さっそく、プログラム全体のコードを示します。

 

 

こちらのコードでは、主に3つ関数によってヒープソートを実現しています。

 

それぞれの関数の説明をします。

 

 

heapSort(52~59行目)

ヒープソート全体をまとめる関数です。

最初に、 build_heap 関数によって、もともとの配列を最大ヒープへと並び替えています。

その後、whileループを使って、ヒープの先頭と末尾の入れ替えを繰り返し行っています。

 

 

 

build_heap(46~50行目)

もともとの配列を最大ヒープへと並び替える関数です。

i = (n / 2) - 1 によって、子を持つギリギリのノードから順番に親子の比較を行います。

 

 

 

down_to_leaf(23~44行目)

選択したノード(親)に対して、親子の比較を繰り返し行う関数です。

40行目のif文で、親子間の交換があった場合に、さらにその下でも同様の処理を繰り返すようになっています。

 

 

一見複雑に見えますが、前の章でしっかりと動作を確認しているため、それと照らし合わせてみることで、理解できると思います。

 

ヒープソートは、割と重要だったりするので、ここまで読んで理解できなかった場合は、もう一度アルゴリズムの流れを確認してみてください。

 

 

では、今回はここまでとします。

お疲れさまでした。

 

別のソートを確認したい方は、ソートアルゴリズム 計算量・特徴一覧をご覧ください。