ヒープソート [Heap Sort]
ヒープソートは整列の対象となる配列の中でヒープ構造を構築しながら整列を行うアルゴリズムです。
整列させたい配列からヒープを構築して、そこから元の配列にコピーして整列を完了させるのではないのです。マージソートのように作業用の領域や、クイックソートのような再帰処理が必要ありません。
アルゴリズム分析
まずは以下のような手順ではないことを理解してください。
- 整列対象の配列から別領域にヒープを構築する
- ヒープから元の配列にデータをコピーする
この方法だとヒープを構築する専用の領域が必要になります。
実際のヒープソートは以下のような手順です。整列対象の配列はN個のデータを持ち、インデックスは1からNとします。
- 整列対象の配列内にボトムアップでヒープを構築する
- 構築されたヒープの先頭要素[1]と最後の要素[N]を交換する
- 要素[1]から要素[N-1]でヒープを再構成する
- ヒープの先頭要素[1]と最後の要素[N-1]を交換する
- 手順3.に戻る
- 手順4.にある最後の要素は[N-2],[N-3]...と移動する
- ヒープ構造がなくなれば整列完了
ヒープのルート要素を配列の末尾の要素へ移動することで整列が行われるのです。
図解
ヒープ構造では配列の先頭に必ず最も大きな(あるいは小さな)値が入ります。したがって、先頭の要素と最後の要素を交換することで整列が実現されるのです。
特徴
ヒープソートは整列対象の配列内でヒープを構築するので整列のための特別な作業領域を必要としないのが特徴です。処理速度はクイックソートなどに劣りますが、膨大なセットを整列させたい場合に作業領域を節約できるので結果的に効率の良いソートが実現できます。
実際のプログラミングではデータを交換するための小さな領域などは使います。
サンプルコード
C言語
配列を昇順に整列させます。
/*
* ヒープソート
* @param numbers ソートする配列
* @param array_size 配列のサイズ
*/
void heap_sort(int* numbers, int array_size)
{
int i, temp;
// ヒープ構築
// 二分木なので親ノードのインデックスは
// (n - 1) / 2 となる
for (i = (array_size - 1) / 2; i >= 0; i--)
{
max_heap(numbers, i, array_size - 1);
}
// ヒープソート実行
// 値を昇順に並べる。
//
// 先頭要素(最大値)を配列の最後に移動させて
// 最後の要素を無視してヒープを構築すると
// 配列内で最も小さな値から順に並ぶ
for (i = array_size - 1; i > 0; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
max_heap(numbers, 0, i - 1);
}
}
/*
* Max-heap を構築する。
*
* 親ノードは子ノードより大きいか等しくなる。
*
* @param numbers ソートしたい配列
* @param root 親ノードとなる要素のインデックス
* @param bottom 最後の要素のインデックス
*/
void max_heap(int* numbers, int root, int bottom)
{
// 子ノードのインデックス
int child = (2 * root) + 1;
// 親ノードの値を保持しておく
int temp = numbers[root];
while (child <= bottom) {
if (child < bottom && numbers[child + 1] > numbers[child]) {
// 二分木のふたつの子ノードから値が大きいほうの子ノードを選択する。
child = child + 1;
}
if (temp > numbers[child]) {
// 親ノードの値が子ノードの値より大きい場合は何もしない。
break;
} else if (temp <= numbers[child]) {
// 親が子より小さいか等しいと
// 親と子を入れ替える
numbers[(child - 1) / 2] = numbers[child];
// 子ノードのインデックスを進める。
child = (2 * child) + 1;
}
}
// 親ノードとなる要素に値を入れる
numbers[(child - 1) / 2] = temp;
return;
}
/*
* Max-heap を構築する。再帰を利用。
*
*/
void max_heap_recursive(int* numbers, int root, int bottom)
{
// 子ノードのインデックス
// 配列の先頭要素のインデックスが 0 なので
// 子ノードは 2n + 1 と 2n + 2 で計算する
int l_idx = (root * 2) + 1;
int r_idx = (root * 2) + 2;
// 最大値を持つ要素のインデックス
int maxChild;
if (l_idx <= bottom && numbers[l_idx] > numbers[root]) {
maxChild = l_idx;
} else {
maxChild = root;
}
if (r_idx <= bottom && numbers[r_idx] > numbers[maxChild]) {
maxChild = r_idx;
}
if (maxChild != root) {
int temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
// 配列の先頭要素には最大値を持つ要素のインデックスを指定する
max_heap_recursive(numbers, maxChild, bottom);
}
}ヒープソートのデモンストレーション プログラム: heap_sort.c
Python
def heapsort(aList):
list_size = len(aList) - 1
for i in range((list_size / 2), -1, -1):
sift_down(aList, i, list_size)
for i in range(list_size , 0, -1):
if aList[0] > aList[i]:
temp = aList[0]
aList[0] = aList[i]
aList[i] = temp
sift_down(aList, 0, i - 1)
return aList
# end def heapsort
def sift_down(aList, root, bottom):
left = root * 2 + 1
right = root * 2 + 2
if left <= bottom and aList[left] > aList[root]:
max_child = left
else:
max_child = root
if right <= bottom and aList[right] > aList[max_child]:
max_child = right
if max_child != root:
aList[root], aList[max_child] = aList[max_child], aList[root]
sift_down(aList, max_child, bottom)
# end def sift_down
if __name__ == '__main__':
from random import randint
l = [randint(0,999) for i in range(7)]
print('Unsorted')
print l
print ('Sorted')
print heapsort(l)
ヒープソートのデモンストレーション プログラム: heap_sort.py
