ヒープソート¶
Tip
本節を読む前に、「ヒープ」の章を学習済みであることを確認してください。
ヒープソート（heap sort）は、ヒープデータ構造に基づいて実装される効率的なソートアルゴリズムです。すでに学んだ「ヒープ構築操作」と「要素の取り出し操作」を利用してヒープソートを実現できます。
- 配列を入力して最小ヒープを構築すると、このとき最小要素はヒープの頂点にあります。
- 取り出し操作を繰り返し実行し、取り出された要素を順に記録すれば、昇順に並んだ列が得られます。
以上の方法でも実行できますが、取り出した要素を保存するために追加の配列が必要となり、空間をやや無駄にします。実際には、通常はより洗練された実装方法を用います。
アルゴリズムの流れ¶
配列の長さを \(n\) とすると、ヒープソートの流れは次図のとおりです。
- 配列を入力して最大ヒープを構築します。完了後、最大要素はヒープの頂点にあります。
- ヒープ頂点の要素（最初の要素）とヒープ末尾の要素（最後の要素）を交換します。交換後、ヒープの長さは \(1\) 減少し、整列済み要素数は \(1\) 増加します。
- ヒープ頂点の要素から始めて、上から下へヒープ化操作（sift down）を実行します。ヒープ化が完了すると、ヒープの性質が回復します。
- 第
2.ステップと第3.ステップを繰り返し実行します。これを \(n - 1\) 回繰り返すと、配列の整列が完了します。
Tip
実際には、要素の取り出し操作にも第 2. ステップと第 3. ステップが含まれており、要素を取り出す処理が 1 つ加わるだけです。
コード実装では、「ヒープ」の章と同じ上から下へのヒープ化 sift_down() 関数を使用します。注意すべき点として、ヒープの長さは最大要素を取り出すたびに短くなるため、sift_down() 関数に長さパラメータ \(n\) を追加し、ヒープの現在の有効な長さを指定する必要があります。コードは以下のとおりです。
アルゴリズムの特性¶
- 時間計算量は \(O(n \log n)\)、非適応ソート：ヒープ構築操作には \(O(n)\) の時間がかかります。ヒープから最大要素を取り出す時間計算量は \(O(\log n)\) であり、これを合計 \(n - 1\) 回繰り返します。
- 空間計算量は \(O(1)\)、インプレースソート：いくつかのポインタ変数が使う空間は \(O(1)\) です。要素の交換とヒープ化操作はいずれも元の配列上で行われます。
- 非安定ソート：ヒープ頂点の要素とヒープ末尾の要素を交換する際、等しい要素どうしの相対位置が変化する可能性があります。