ヒープソートの最適化

前の節のヒープソートでは、追加のスペースを確保してヒープを構築し、ヒープをソートしました。この節では、インプレースヒープソートを使用して最適化します。

最大ヒープの場合、まず先頭位置のデータと配列の末尾の値を交換します。すると配列の末尾が最大要素になります。次に、そのW要素に対して shift down 操作を行い、最大ヒープを再生成します。その後、新しく生成された最大値と配列全体の末尾から2番目の位置を交換します。このとき、末尾から2番目の位置が2番目に大きなデータになります。このプロセスを以下同様に繰り返します。

全体のプロセスは、次の図のように表すことができます:

Java サンプルコード

ソースコードパッケージのダウンロード:Download

src/サンプル/heap/HeapSort.java ファイルコード:

package サンプル.heap;

import サンプル.sort.SortTestHelper;

/**
* インプレースヒープソート
 */

public class HeapSort<T extends Comparable> {


    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // 注意:ここでのヒープのインデックスは0から始まります
        // (最後の要素のインデックス - 1) / 2 から始めます
        // 最後の要素のインデックス = n-1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            shiftDown(arr, n, i);
       
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // ヒープ内のインデックスが i と j の2つの要素を交換します
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 元のshiftDownプロセス
    private static void shiftDown(Comparable[] arr, int n, int k) {

        while (2 * k + 1 < n) {
            //左の子ノード
            int j = 2 * k + 1;
            //右の子ノードが左の子ノードより大きい
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
                j += 1;
            //両方の子ノードより大きい
            if (arr[k].compareTo(arr[j]) >= 0) break;
            //元のノードと子ノードの値を交換します
            swap(arr, k, j);
            k = j;
        }
    }

    // HeapSort をテストする
    public static void main(String[] args) {

        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // heapify 内のデータを extractMax で少しずつ取り出します
        // 取り出す順序は大きいものから小さいものの順になります
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        // arr 配列が大きいものから小さいものの順に並んでいることを確認します
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}
その他の拡張