本記事では、基本的なソートの一種である「ヒープソート」のアルゴリズム解説・C言語による実装を確認していきます。
アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。
図を多く挿入しているため、ページとしては結構長めです。
ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。
- ヒープソートの基本的な情報
- アルゴリズムの流れ
- C言語による実装方法
こちらの記事で、他のソートアルゴリズムをまとめています。
アルゴリズム入門書はこの一冊で十分！
ヒープソートとは
ヒープソートは、ソートアルゴリズムの一種であり、ヒープ構造を利用したソートです。
ちなみに、ヒープは「優先度付きキュー」などと呼ばれることもあります。
ヒープソートの基本的な情報は以下のようになります。
| 最悪計算時間 \(O\) | 安定性 |
| \(O(nlog(n))\) | 安定ではない |
ヒープソートの計算時間は、\(O(nlog(n))\)であるため、ソートの中では高速に動作する部類です。
では、次の章から、実際のヒープソートのアルゴリズムを見ていきましょう。
ヒープソートのアルゴリズム
ヒープソートのアルゴリズムをわかりやすく説明するために、以下のように、順を追って解説を進めていきます。
- そもそもヒープとは
- ヒープソートアルゴリズムの全体的な流れ
- ヒープソートアルゴリズムの具体的な動き
１では、ヒープの説明をします。
２では、１の説明をもとに、ザックリとしたヒープソート全体の流れを確認します。
３では、２で確認した動きをどのように実現するのかを確認・解説します。
では、さっそく見ていきましょう！
そもそもヒープとは
ヒープは、データ構造の一種であり、普通の配列を二分木として扱うための構造です。
二分木はポインタを使用して実装することが一般的ですが、普通の配列を使用して実装することで、アクセス時間が短縮できるという利点があります。
具体例を出すと、サイズが１０の配列は、以下のように二分木として扱います。
画像からわかるように、配列の先頭がルートとなり、添え字が１, ２の要素は深さ１のノード、添え字が3，4，5，6の要素は深さ２のノード、、、といった具合です。
基本的には左詰めで考えます。
何か特別な操作をしたというよりは、「横一列の配列を、こんな感じの二分木として扱いますよ」という、ただそれだけのことです。
まだ、しっくりこないかもしれないので、別の配列を見てみます。
今度は、以下のような配列でヒープを考えてみます。
ヒープは、形式的に配列の見方を変えるだけなので、以下のような二分木として扱うことになります。
以上がヒープの説明です。
ヒープソートでは、最大ヒープという並び方を利用するので、こちらの説明もしておきます。
最大ヒープは、上の説明に毛が生えたような話なので、気楽に読んでください。
上で確認した配列は、特に規則のない並び方でした。
最大ヒープでは、二分木として見た場合に、ある条件を満たすように配列を並び替えます。
その条件は、すべてのノードにおいて「親」＞「子」の関係が成り立つ、というものです。
こちらも具体例を見てみましょう。
例えば、さきほど上で確認した配列を最大ヒープに並び替えると、以下のようになります。
※最大ヒープは一通りだけではないです。
配列として見た場合は、特に規則があるようには見えませんね。
しかし、これを二分木として見た場合は、以下のようになります。
この二分木は、自分より上にある要素が、自分よりも大きな値になっていますね。
つまり、「親」＞「子」を満たしているということです。
これが最大ヒープです。
ちなみに、最小ヒープというものもありますが、これは最大ヒープの逆だと思ってもらえればOKです。
すべてのノードで「親」＜「子」の関係が成立している、ということですね。
今回は出てこないのですが、一応セットで覚えておきましょう。
これで、最大（最小）ヒープの説明まで終わりました。
では、最大ヒープの構造を踏まえた上で、これをどのように利用するのかを見ていきましょう。
ヒープソートアルゴリズムの全体的な流れ
ここでは、具体的な処理を確認する前に、ザックリとソートの手順を図で確認していきます。
さきほど、最大ヒープを確認しましたね。
ヒープソートでは、この最大ヒープをうまく利用することで、配列全体をソートします。
これは、言葉で説明するよりも図を見た方がわかりやすいので、さっそく図へ移りましょう。
今回は、具体例として、サイズ８の配列をソートすることにします。
まずは、この配列をヒープ構造として見ます。
再度確認しますが、これは形式的に見方を変えただけです。
これを最大ヒープに並び替えてみましょう。
どのように最大ヒープに並び替えるのかは、後ろの方で説明します。
最大ヒープに並び替えることで、嬉しいことが１つあります。
それは、「必ずヒープのてっぺんに最大値が来る」という点です。
ヒープのてっぺんは、配列の先頭なので、最大値を取得するまでの計算時間は\(O(1)\) で済みます。
これが、ヒープソートが高速に動作する理由の１つです。
では、次に、配列の先頭に移動してきた最大値を、ヒープの末尾と取り換えます。
この時、配列は以下のように変化しています。
これは、配列中の最大値が一番後ろに移動した、ということです。
今度は、ヒープサイズを1つ減らして、再び最大ヒープに並び替えます。
「ヒープサイズを１つ減らす」、というのは、単純に配列の末尾を無いものとして扱うということです。
これは、もともとの配列における最大値の次に大きな値が、配列の先頭に移動していることになります。
今回、配列中の最大値「９」は、ヒープに含んでいないため、その次に大きな「８」がヒープのてっぺんに来ている、ということです。
では、同様にして、先頭とヒープの末尾を入れ替えます。
このとき、「９」はヒープから除外して考えているため、ヒープの末尾は「１」になります。
配列はこのように変化します。
ここまで見ると察しがつくかと思いますが、あとはこれを繰り返すだけで、配列の後ろから順番に大きな値が並んでいきます。
イメージとしては、木のてっぺんにあるヒープの最大値を、ひたすら配列の奥へと詰め込んでいく感じです。
念のため、もう１セット確認します。
まずは、ヒープのサイズを１つ減らします。
つまり、今度は「８」と「９」を無いものとして扱う、ということです。
そして、再び最大ヒープに並び替えます。
次に、ヒープの末尾と先頭を入れ替えます。
今回は、「８」と「９」をヒープに含んでいないため、ヒープの末尾は「３」になりますね。
配列はこのようになります。
ここまでの処理を繰り返すことで、配列の後ろから順番にソートが完了します。
配列の中で、ヒープに含まれない部分だけに着目すると、こんな感じでソートが進みます。
本来は、この空白部分で、何度も最大ヒープへの並び替えが行われています。
ソートの全体的な流れを確認することができたので、残りは具体的なアルゴリズムを確認するだけです。
いよいよ終盤なので、最後まで頑張りましょう！
ヒープソートアルゴリズムの具体的な動き
ヒープソートの流れを再度確認します。
- 最大ヒープに並び替える
- ヒープの先頭と、ヒープの末尾を入れ替える
- ヒープサイズを１つ減らす
- ヒープサイズが2つ以上であれば①へ戻る
ヒープソートの流れはすでに確認済みであるため、ここでは、「いかにして最大ヒープへと並び替えるのか」を解説します。
最大ヒープへ並び替える方法さえわかれば、あとは上で確認した処理を繰り返すだけでソートできますね。
では、最大ヒープへの並べ替え方を解説していきます。
最大ヒープは、すべてのノードにおいて「親」＞「子」が成立すればいいわけでしたね。
なので、ここは単純に、「親」＜「子」となっている部分を入れ替えていけばよさそうです。
図で見てみましょう。
最初のヒープをこうだとします。
「親」＜「子」となっている部分がいくつかありますね。
では、その部分を入れ替えていきましょう、と言いたいところですが、一体どこから手を付けるべきでしょうか。
これは、二分木の下側から入れ替えていく、が正解になります。
上からでもできないことは無いのですが、かなり効率が悪くなります。
気になる方は、下側から手を付けるパターンを確認したあとに、同様の処理を上からやってみてください。
では、下側かつ子を持つ親から順番に、以下の処理を行います。
これは、親の視点から見た処理の説明です。
- 左右の子と自分（親）の値を比較
- 自分（親）よりも子が大きい場合は交換
- 交換後にも子を持つのであれば、①へ戻る
まずは、下側から順番に、子を持つ親を探していきます。
「下側から順番に」は、黄色の矢印と逆の順番のことです。
つまり、上の図で言うと、「６」→「９」→「３」→「７」→ 、、、といった具合です。
その中で、最初に子を持つ親を決定します。
最初に着目する値は、「１」になりますね。
次に、親と子を比較します。
今回の例だと、「１」と「６」の比較です。
このとき、「親」＜「子」であれば、それらを交換します。
では、交換しましょう。
交換後、着目していた値「１」は子を持たないので、これで１つの処理が終了です。
着目する値を変更して、同様の処理を繰り返します。
次に着目する親は、「８」です。
では、親と子を比較しましょう。
今回は、親の「８」と、子の「３」「９」の比較を行います。
この中で、親より大きい値は「９」なので、それらを交換します。
交換後、着目していた親「８」は子を持たないので、ここで１つの処理が終了です。
再び着目する親を変更します。
次に着目する親は「２」です。
次は、親の「２」と、子の「６」「７」を比較します。
今回は、左右両方の子が親よりも大きい値ですね。
この場合は、その中でも大きな方と交換します。
つまり、「２」と「７」を交換するということです。
交換後、着目していた親「２」は子を持たないので、ここで１つの処理が終了です。
再び着目する親を変更します。
最後に着目する親は「４」です。
親「４」と、子「７」「９」を比較します。
今回もまた、左右両方の子が親よりも大きな値です。
この場合は、「４」と「９」を交換するんでしたね。
今まで見てきた場合と違って、交換後に、着目している親「４」は子を持っています。
なので、再び親と子の比較をします。
今度は、着目していた親「４」は子を持たないので、これで終了です。
また、着目する値も一番上前まで来たので、すべての処理がおしまいになります。
確認してみると、これは、すべてのノードにおいて「親」＞「子」の関係が成り立っていますね。
ここまでが、最大ヒープへの並べ替え方です。
次の章では、これをC言語で実装していきます。
実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。
ヒープソートの実装【C言語】
さっそく、プログラム全体のコードを示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <stdio.h> #define N 8 // 配列の全ての要素を出力する void printArray(int A[], int n) { for (int i = 0; i < n; i++) if (i == 0) printf("%d", A[i]); else printf(" %d", A[i]); printf("\n"); } // 配列の要素を入れ替える void swap(int A[], int a, int b) { int temp; temp = A[a]; A[a] = A[b]; A[b] = temp; } void down_to_leaf(int A[], int n, int target) { int left = target * 2 + 1; int right = target * 2 + 2; int max_idx = target; // left が存在する場合、target と比較 if (left < n) if (A[target] < A[left]) max_idx = left; // right が存在する場合、max_idx と比較 if (right < n) if (A[max_idx] < A[right]) max_idx = right; // target より大きい値があれば交換 // down_to_leaf を再帰的に呼び出す if (target != max_idx) { swap(A, target, max_idx); down_to_leaf(A, n, max_idx); } } void build_heap(int A[], int n) { // ヒープの初期化 for (int i = (n / 2) - 1; i >= 0; i--) down_to_leaf(A, n, i); } void heapSort(int A[], int n) { build_heap(A, n); while (n > 1) { swap(A, 0, --n); // ヒープサイズを 1 減らす down_to_leaf(A, n, 0); } } int main(void) { int A[N] = {4, 2, 8, 1, 7, 3, 9, 6}; printArray(A, N); heapSort(A, N); // ヒープソートを行う printArray(A, N); return 0; } |
こちらのコードでは、主に３つ関数によってヒープソートを実現しています。
それぞれの関数の説明をします。
heapSort（52~59行目）
ヒープソート全体をまとめる関数です。
最初に、 build_heap 関数によって、もともとの配列を最大ヒープへと並び替えています。
その後、whileループを使って、ヒープの先頭と末尾の入れ替えを繰り返し行っています。
|
52 53 54 55 56 57 58 59 |
void heapSort(int A[], int n) { build_heap(A, n); while (n > 1) { swap(A, 0, --n); // ヒープサイズを 1 減らす down_to_leaf(A, n, 0); } } |
build_heap（46~50行目）
もともとの配列を最大ヒープへと並び替える関数です。
i = (n / 2) - 1 によって、子を持つギリギリのノードから順番に親子の比較を行います。
|
50 51 52 53 54 |
void build_heap(int A[], int n) { // ヒープの初期化 for (int i = (n / 2) - 1; i >= 0; i--) down_to_leaf(A, n, i); } |
down_to_leaf（23~44行目）
選択したノード（親）に対して、親子の比較を繰り返し行う関数です。
40行目のif文で、親子間の交換があった場合に、さらにその下でも同様の処理を繰り返すようになっています。
|
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
void down_to_leaf(int A[], int n, int target) { int left = target * 2 + 1; int right = target * 2 + 2; int max_idx = target; // left が存在する場合、target と比較 if (left < n) if (A[target] < A[left]) max_idx = left; // right が存在する場合、max_idx と比較 if (right < n) if (A[max_idx] < A[right]) max_idx = right; // target より大きい値があれば交換 // down_to_leaf を再帰的に呼び出す if (target != max_idx) { swap(A, target, max_idx); down_to_leaf(A, n, max_idx); } } |
一見複雑に見えますが、前の章でしっかりと動作を確認しているため、それと照らし合わせてみることで、理解できると思います。
ヒープソートは、割と重要だったりするので、ここまで読んで理解できなかった場合は、もう一度アルゴリズムの流れを確認してみてください。
では、今回はここまでとします。
お疲れさまでした。
別のソートを確認したい方は、ソートアルゴリズム 計算量・特徴一覧をご覧ください。