ヒープソート

ヒープソートとは

ヒープソートは、二分ヒープ木というデータ構造を用いてリスト（配列）を並び替えるソートアルゴリズムです。このアルゴリズムは、ヒープ領域とは直接関係がないことに注意が必要です。

ヒープソートは以下の2つの主要な段階で構成されます。

1. ヒープ構築：
- 未整列のリストから要素を1つずつ取り出し、二分ヒープに追加します。この操作をすべての要素がヒープに追加されるまで繰り返します。
2. ソート：
- ヒープのルート（最大値または最小値）を取り出し、ソート済みリストに追加します。この操作をすべての要素がヒープから取り出されるまで繰り返します。

このアルゴリズムの計算量はO(n log n)であり、安定ソートではありません。これは、同じ値を持つ要素の相対的な順序がソート後に保持されない可能性があることを意味します。

アルゴリズムの詳細

ヒープ構造は、ポインタなどの制御用データを使用せず、データの並び順（配列）だけで表現できるという利点があります。ヒープソートの実装では、この利点を活用して、元のデータ領域をそのままヒープ構造やソート済みリストとして使用する、インプレースソートとして実装されることが一般的です。

ヒープ構築のステップ

まず、N個のデータを含む配列が与えられたとします。配列のインデックスは1からNまでとします。

1. ヒープへの要素の挿入：
- 配列の各データをヒープ構造に順番に登録していきます。m個のデータを処理した状態では、配列のインデックス1からmまでがヒープ構造であり、インデックスm+1からNまでが未整列のリストとなります。
- 次に、m+1番目のデータを取り出し、ヒープ構造に登録します。この時、昇順にソートする場合はルートが最大値になるように、降順にソートする場合はルートが最小値になるようにヒープを構成します。

ソートのステップ

2. ヒープからの要素の取り出し：
- すべてのデータをヒープ構造に登録し終えたら、ヒープからの取り出しを開始します。
- ヒープのルートを取り出し、配列の後ろから順に詰めていきます。mをNから1まで減らしながら、取り出したルート要素を配列のインデックスmに置きます。つまり、(N-m)個のデータを取り出した状態では、インデックス1からmまでがヒープ構造で、インデックスm+1からNまでがソート済みリストとなります。

3. ソート完了：
- すべてのデータをヒープ構造から取り出し終えると、配列全体がソートされた状態になります。

ヒープの操作の具体的な実装については、二分ヒープの記事を参照してください。

一般的に、ヒープ操作では木の根側から成長させるのが一般的ですが、配列のようなデータ構造のヒープソートでは、木の最終的な大きさが事前に分かっている場合、木の葉側から順番にヒープを構築すると、より効率が向上します。ただし、この記事に示す実装例では、この手法は使用していません。

実装例

以下に、ヒープソートの実装例を示します。この実装例は、原理と一般的な手法を説明するために、細かい最適化は行っていません。

python
def heapify(arr, n, i):
largest = i
left = 2 i + 1
right = 2 i + 2

if left < n and arr[i] < arr[left]:
largest = left

if right < n and arr[largest] < arr[right]:
largest = right

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr):
n = len(arr)

for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)

return arr

実装の補足

上記の実装では、ヒープソートの原理と一般的な手法を示しています。より効率を高めるための細かいチューニングはしていません。例えば、以下のような改善点が考えられます。

- ルートの要素を番兵として利用し、比較回数を減らす。
- スワップ操作の代わりに、一時変数を使用して無駄なメモリ書き込みと読み込みを削減する。
- ヒープの最終的な大きさが既知の場合、木の葉側からヒープを構築する。

これらの改善点については、『珠玉のプログラミング』の該当コラムで詳しく解説されています。

特徴

ヒープソートには以下のような特徴があります。

- 計算量の安定性：データの出現順序による計算量の変動が比較的小さいです。クイックソートのように最悪の場合にO(n^2)となることはありません。ただし、平均的にはクイックソートの方が高速です。
- 追加のメモリ消費：ソート対象のデータ以外に必要な作業領域の大きさは固定されており、データ量に依存しません（インプレースソート）。

しかし、ヒープソートには現代のコンピュータにおける高速化技法に適さない以下の点もあります。

- 並列化の難しさ：並列処理による高速化が難しい。
- メモリアクセスの局所性の低さ：ヒープ構造はメモリへのアクセスが連続しておらず、ランダムアクセスになりがちです。そのため、キャッシュの効率が悪く、空間的局所性が低いといえます。

脚注

- このアルゴリズムのヒープ構造は、ヒープ領域とは無関係です。

参考文献

- ジョン・ベントリー『珠玉のプログラミング』（コラム14）小林健一郎訳、ピアソン・エデュケーション、2000年、ISBN 4-89471-236-9。

外部リンク

- Heapsort code

もう一度検索

ヒープソート