ヒープソート
(heap sort から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/17 06:13 UTC 版)
 ヒープソートのアルゴリズムがランダムな数字の列に対して動作する例。アルゴリズムの第一ステージでは、配列の要素をヒープ条件を満すように並べている。その後、実際にソート済みの場所に並びかえる前に、ヒープ構造がイラストの上に表れている。 | |||||||||||||
| クラス | ソート | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| データ構造 | 配列 | ||||||||||||
| 最悪計算時間 |
まず各データをヒープ構造に登録していく。m個のデータを処理した状態では、添字1 〜 mがヒープ構造で、(m + 1) 〜 Nが未整列リストとなる。m + 1個目のデータを取り出し、ヒープ構造に登録する。このとき構成するヒープは、昇順にソートする場合はルートが最大値になるよう、降順にソートする場合はルートが最小値になるよう構成する。  すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しに移る。ヒープのルートを取り出し、配列の後ろから詰めていく。mを Nから1まで減しながら、取り出したルート要素を配列の添字mに置く。すなわち、(N - m)個のデータを取り出した状態では添字1 〜 mがヒープ構造であり、m + 1 〜 Nが整列済みリストとなる。 すべてのデータをヒープ構造から取り出し終えると、配列全体が整列済みになる。 ヒープの操作の具体的な実装については、二分ヒープの記事を参照すること。 また、一般のヒープ操作では、根元側から木を成長させるのが普通だが、配列のようなデータ構造のヒープソートで、あらかじめ木の最終的な大きさがわかっている場合は、木の葉の側から順番にヒープを構築すると、より効率が良い（この記事で示す実装例では使っていない）。 実装例static void upheap(double arr[], int n);
static void downheap(double arr[], int n);
static inline void
swap(double arr[], int a, int b)
{
double tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void
heapsort(double arr[], int n_elems)
{
int i = 0;
/*
* arr の先頭から順に、ヒープを成長させる
* 0 1 2 | 3 4 5
* [ ] [ ] [ ]|[ ] [ ] [ ]
* ヒープ | 未処理の入力
* ===>
* i は、ヒープ中の要素数であると同時に、未処理データの先頭を
* 指してもいる
*/
/* 配列が全部ヒープに入れ替わるまで繰り返す */
while (++i < n_elems) {
/*
* 配列の先頭要素を、ヒープの最後に移動するわけだが、どちらも
* ちょうど同じ場所に最初からあるので、境界を移動させるだけでよい
*/
/*
* arr[i] に、ヒープに新しく追加されたデータがあるものとして、
* 先頭から arr[i] までがヒープになるよう再構成する
*/
upheap(arr, i);
}
/*
* arr の末端から順に、ヒープから取り出して並べる
* 0 1 2 | 3 4 5
* [ ] [ ] [ ]|[ ] [ ] [ ]
* ヒープ | ソート済みの配列
* <===
*/
/* ヒープが全部配列に入れ替わるまで繰り返す */
while (--i > 0) {
/*
* ヒープの先頭要素を、配列に移動すると同時に、ヒープの最後の
* 要素を、ヒープの先頭に移動する swap
*/
swap(arr, 0, i);
/*
* arr[0] に、ヒープの最後から移動されたデータがあるものとして、
* 先頭から arr[i - 1] までがヒープになるよう再構成する
*/
downheap(arr, i);
}
}
/*
* macros for heaptree
* for 0 origin array
*/
#define LEFT_CHILD(i) (((i) + 1) * 2 - 1)
#define RIGHT_CHILD(i) (((i) + 1) * 2)
#define PARENT(i) (((i) + 1) / 2 - 1)
/*
* arr[n] に、ヒープに新しく追加されたデータがあるものとして、
* 先頭から arr[n] までがヒープになるよう再構成する
*/
static void
upheap(double arr[], int n)
{
while (n > 0) {
int m = PARENT(n);
if (arr[m] < arr[n]) {
swap(arr, m, n);
} else {
break;
}
n = m;
}
}
/*
* arr[0] に、ヒープの最後から移動されたデータがあるものとして、
* 先頭から arr[n - 1] までがヒープになるよう再構成する
*/
static void
downheap(double arr[], int n)
{
int m = 0;
int tmp = 0;
for (;;) {
int l_chld = LEFT_CHILD(m);
int r_chld = RIGHT_CHILD(m);
if (l_chld >= n) {
break;
}
if (arr[l_chld] > arr[tmp]) {
tmp = l_chld;
}
if ((r_chld < n) && (arr[r_chld] > arr[tmp])) {
tmp = r_chld;
}
if (tmp == m) {
break;
}
swap(arr, tmp, m);
m = tmp;
}
}
補足ここで示した実装では原理と一般的な手法を示すため、細かいチューニングはしていない。ルートの要素を番兵にして比較を節約する、スワップではなくループの外で定義した一時変数に退避するようにして無用な「書いたものを読んで」を減らす、最初からヒープの最終的な大きさがわかっているので、木を葉のほうから構築する、といった改善が可能な点がある（参考文献『珠玉のプログラミング』の該当コラムの「問題」の節と巻末の解説を参照のこと）。 特徴
ただし以下のように、現代のコンピュータで用いられる高速化技法に適さない特徴があることにも注意する必要がある。 脚注関連項目参考文献
外部リンクヒープソートと同じ種類の言葉
「ヒープソート」の関連用語
検索ランキング
ヒープソートのページの著作権
ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
©2025 GRAS Group, Inc.RSS | ||||||||||||
