no_mkd
一. ヒープソートの長所と短所（pros and cons）
（この点について簡単に触れておきます。出来の悪いアルゴリズムを理解するために時間を無駄にする必要はありませんから。）
長所：
- ヒープソートの効率はクイックソートやマージソートと同じく、比較に基づくソートアルゴリズムの効率のピーク（時間計算量 O(n log n)）に達しています。
- 効率的なだけでなく、最大のハイライトは O(1) の補助空間しか必要としないことです。最高効率でありながら最も省スペースである、唯一無二の存在です。
- ヒープソートの効率は比較的安定しています。クイックソートのように最悪の場合に時間計算量が O(n^2) になることがありません。ソート対象のシーケンスがソート済みかどうかにかかわらず、ヒープソートの効率は常に O(n log n) です（ここでの「安定」は、平均時間計算量 ＝ 最悪時間計算量という意味であり、ソートの「安定性」のことではありません。ヒープソート自体は不安定なソートです）。
短所：（上記を見るとヒープソートはほぼ完璧に見えますが、なぜ最も一般的に使われる内部ソートアルゴリズムはヒープソートではなくクイックソートなのでしょうか？）
- 最大かつ唯一の欠点は、ヒープの維持管理の問題です。実際のシナリオにおけるデータは頻繁に変動しますが、ソート対象のシーケンスが更新（追加、削除、変更）されるたびに、ヒープの特性を維持するためにヒープの再構築を行う必要があります。これは多くの場合、不要なコストとなります。（そのため、クイックソートが実用上の王者となり、ヒープソートはアルゴリズムの教科書の中で光り輝く存在となっています。もちろんこう言うのは少し言い過ぎですが、データの更新がそれほど頻繁でない場合は、当然ヒープソートの方が優れています…。）
二. 内部原理
まず、ヒープソートの手順を知る必要があります：
- 初期ヒープの構築：ソート対象のシーケンスに基づいて、最初の最大ヒープまたは最小ヒープを構築します（最大ヒープ、最小ヒープとは何か？これについては説明しません。積み上げられた藁の山を想像してください…）。
- 先頭と末尾の交換、末尾の切り離しと再構築：末尾を切り離した後、残りの部分に対して最大（最小）ヒープを再構築します。
- 手順2を、先頭と末尾が重なるまで（すべての要素が切り離されるまで）繰り返して完了です。
最小ヒープによるソート結果は降順（正確には非昇順ですが、細かいことは気にしないでください…）、最大ヒープによるソート結果は昇順になります。
上記の文は一見間違っているように見えるかもしれません（最小ヒープでは最小の要素がヒープの頂点、つまり配列の a[0] に来るのに、なぜ降順になるのか？）。しかし、この記述の正しさを疑う必要はありません。以下の図を見れば理解できるはずです：
ソート対象のシーケンスを a[] = {7, 1, 6, 5, 3, 2, 4} とし、最大ヒープ方式でソートを行うと仮定します。
手順1（初期ヒープの構築）：
{7, 5, 6, 1, 3, 2, 4} はすでに最大ヒープの条件を満たしており、手順1が完了しました。
手順2（先頭と末尾の交換、末尾の切り離しと再構築）：
手順3（すべての末尾が切り離されるまで手順2を繰り返す）：
図はありません。描くのに疲れました、mspaintは本当に使いにくいです…。手順2まで見れば十分でしょう。残りはペンで描いてみればわかるはずです…。
核となるのは「末尾の切り離し」ですが、悲しいことにどの資料にも明確には書かれていません。しかし、「末尾の切り離し」以上に適切な表現があるでしょうか？
三. 実装の詳細
原理解説の図で実装の詳細もほぼ説明されているので、ここではコードの実装に注目します。
まず、自力で書いた最大ヒープ方式の実装です：
#include<stdio.h>// 最大ヒープの構築（a[m]からa[n]までを最大ヒープの条件に合わせる） void HeapAdjust(int a[], int m, int n){ int temp; int max; int lc;// 左の子 int rc;// 右の子
while(1){ // a[m] の左右の子を取得 lc = 2 * m + 1; rc = 2 * m + 2; // 左右の子を比較し、maxに大きい方のインデックスを記録 if(lc >= n){ break;// 左の子が存在しなければループを抜ける } if(rc >= n){ max = lc;// 右の子が存在しなければ、最大の子は左の子となる } else{ max = a[lc] > a[rc] ? lc : rc;// 左右どちらも存在すれば、大きい方のインデックスを探す } // 判断と調整（交換） if(a[m] >= a[max]){// 親が左右の子よりも大きければ調整不要、ループを抜ける break; } else{// そうでなければ、小さい親を下へ入れ替える temp = a[m]; a[m] = a[max]; a[max] = temp; // 次のループの準備。注目点を子に移動させる。交換により、その子を根とする部分木が最大ヒープの条件を満たさなくなる可能性があるため m = max; } }}
void HeapSort(int a[], int n){ int i,j; int temp;
// 下から上に向かって最大ヒープを構築（初期ヒープ） for(i = n / 2 - 1;i >= 0;i--){// a[n/2 - 1] は最後の非葉ノード（葉ノードはすでに条件を満たしているため、非葉ノードのみ調整すればよい）。小さな最適化 HeapAdjust(a, i, n); } printf("初期ヒープ: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); for(i = n - 1;i > 0;i--){ // 先頭と末尾を交換し、末尾を切り離す temp = a[i]; a[i] = a[0]; a[0] = temp; // 切り離した後の残りの部分を再調整 HeapAdjust(a, 0, i); /* printf("第%d回（i - 1 = %d）: ", n - i, i - 1); for(j = 0;j < n;j++){ printf("%d ", a[j]); } printf("\n"); */ }}
main(){ //int a[] = {5, 6, 3, 4, 1, 2, 7}; //int a[] = {1, 2, 3, 4, 5, 6, 7}; //int a[] = {7, 6, 5, 4, 3, 2, 1}; int a[] = {7, 1, 6, 5, 3, 2, 4}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("結果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. コード内のコメントは非常に詳しく書きました。完全に一歩ずつ自分で考えながら書いたので、理解するのは難しくないはずです。コードを見て判断してください。ここで多くを語る必要はないでしょう。
次に、書籍に載っているような最大ヒープ方式の実装を紹介します：
#include<stdio.h>void HeapAdjust(int a[], int m, int n){ int i; int t = a[m];
for(i = 2 * m + 1;i ≤ n;i = 2 * i + 1){ if(i < n && a[i + 1] > a[i])++i; if(t >= a[i])break; // 空いた位置を下へ移動させる a[m] = a[i]; m = i; } a[m] = t;// 交換を一度だけ行う、手順上の最適化}
void HeapSort(int a[], int n){ int i; int t;
// 下から上に向かって最大ヒープを構築 for(i = n / 2 - 1;i >= 0;--i){ HeapAdjust(a, i, n - 1); } printf("初期ヒープ: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); for(i = n - 1;i > 0;i--){ // 先頭と末尾を交換し、末尾を切り離す t = a[i]; a[i] = a[0]; a[0] = t; // 切り離した後の残りの部分に対してヒープを再構築 HeapAdjust(a, 0, i - 1); }}
main(){ //int a[] = {5, 6, 3, 4, 1, 2, 7}; //int a[] = {1, 2, 3, 4, 5, 6, 7}; //int a[] = {7, 6, 5, 4, 3, 2, 1}; int a[] = {7, 1, 6, 5, 3, 2, 4}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("結果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. 書籍のコードはかなり短くなっています。これは単なる記述量の削減ではなく、実質的な手順の最適化が行われているからです。その微妙な違いもコメントに記しました。しかし、このレベルの最適化はコードの可読性を大幅に下げてしまいます。アルゴリズムの本を手に取っては、また置いてしまう理由がこれです…（実際の開発では、書籍のコードを形式的にリファクタリングし、効率を維持しつつ可読性を最大限に高めることができます）。
最後に、書籍のアルゴリズムを研究した上でその最適化手法を取り入れ、自分で書いた最小ヒープ方式の実装です（ネット上の資料は最大ヒープのものが多いですが、原理は同じです。ここでは単調さを避けるために最小ヒープにしました…）：
#include<stdio.h>// 最小ヒープの構築（a[m]からa[n]までを最小ヒープの条件に合わせる） void HeapAdjust(int a[], int m, int n){ int i; int t = a[m]; int temp;
for(i = 2 * m + 1;i ≤ n;i = 2 * i + 1){ // a[m] の左右の子を比較し、iに小さい方のインデックスを記録 if(i < n && a[i + 1] < a[i]){ i = i + 1; } if(t <= a[i]){ break; } else{// 空いた位置を下へ入れ替える // 小さい方を上へ入れ替える temp = a[m]; a[m] = a[i]; a[i] = temp; // 次のループの準備 m = i; } }}
void HeapSort(int a[], int n){ int i, j; int temp;
// 下から上に向かって最小ヒープを構築（初期ヒープ） for(i = n / 2 - 1;i >= 0;i--){// a[n/2 - 1] は最後の非葉ノード。小さな最適化 HeapAdjust(a, i, n); } printf("初期ヒープ: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); // 各要素を適切な位置に調整する for(i = n - 1; i > 0;i--){ // 先頭と末尾を交換 temp = a[i]; a[i] = a[0]; a[0] = temp; // 末尾を切り離した後の残りの部分を再調整 HeapAdjust(a, 0, i - 1); }}
main(){ //int a[] = {7, 6, 5, 4, 3, 2, 1}; //int a[] = {1, 5, 6, 4, 3, 2, 7}; int a[] = {1, 2, 3, 4, 5, 6, 7}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("結果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. コメントは引き続き詳細に書いてあります。コードを見てください、余計な説明はしません。
四. まとめ
ヒープソートの手順はわずか数語で表せます：ヒープ構築 -> 先頭と末尾の交換、末尾の切り離しと再構築 -> すべての末尾が切り離されるまで手順2を繰り返す
これ以上に明快な説明があるでしょうか？
これで私たちはいくつかの有用なソートアルゴリズムを習得しました：
では、実務でどのように選択すべきでしょうか？以下のような基準があります：
- n が小さい場合は、挿入ソートか単純選択ソートを採用します。直接挿入ソートは単純選択ソートよりも記録の移動回数が多いため、記録自体の情報量が大きい場合は、単純選択ソートの方が適しています。
- ソート対象のシーケンスがほぼソートされている場合は、直接挿入ソートかバブルソートを採用します。
- n が大きい場合は、時間計算量が最も低いアルゴリズム、すなわちクイックソート、ヒープソート、またはマージソートを採用すべきです。
-
- 細かく分けると、データがランダムに分布している場合はクイックソートが最適です（これにはクイックソートのハードウェア最適化が関係しており、以前のブログ記事でも触れました）。
- ヒープソートは補助空間を一つしか必要とせず、クイックソートのような最悪のケースも発生しません。
- クイックソー��とヒープソートはどちらも不安定なソートです。安定性が求められる場合はマージソートを採用できます。また、直接挿入ソートとマージソートを組み合わせ、まず直接挿入でソート済みの断片を作り、それをマージしていく方法もあります。直接挿入は安定しているため、この結果も安定したものになります。
補足：「末尾の切り離し」を理解する過程で先人のブログ記事を参考にしました。ここに感謝申し上げます。
コメントはまだありません