ヒープソート | アルゴリズム [AOJ 10029][Java]

今回は、『AOJ 10029 - ソートアルゴリズム』を非ヒープソートを使って解いてみました。Javaのサンプルソースを載せています。

algorithm-heap-sort

😸 ヒープとは?

ヒープとは親が子の値以上であるという条件を満たす完全2分木
子をもつノードの値は、2つの子のどちらの値よりも大きい (逆でも可)

🎉 特徴

チャンピオンシップ・トーナメントの振る舞い
単純選択ソートの応用的アルゴリズム
クイックソートの苦手な入力に対しても期待どおりの性能を発揮する
平均時性能はクイックソートに負ける

😀 親インデックスと子インデックスの関係

要素 a[i] に対して：
- 親は a[(i-1)/2] (余剰は切り捨て)
- 左の子は、a[i*2+1]
- 右の子は、a[i*2+2]

🚌 AOJ問題

AOJ 10029 - ソートアルゴリズム

🍄 Javaコード

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] a) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(r.readLine());
        String[] str = r.readLine().split(" ");

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }

        arr = buildHeap(arr);

        int tmp;
        for (int i = n - 1; i >= 1; i--) {
            tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            heapify(arr, 0, i);
        }

        StringBuilder s = new StringBuilder();
        for (int i = 0; i < n; i++) {
            s.append(arr[i]);
            if (i != n - 1) {
                s.append(" ");
            }
        }
        System.out.println(s);
    }

    private static int[] buildHeap(int[] arr) {
        int[] result = new int[arr.length];
        for (int i = arr.length/2 - 1; i >= 0; i--) {
            result = heapify(arr, i, arr.length);
        }
        return result;
    }

    private static int[] heapify(int[] arr, int index, int maxIndex) {
        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;

        int largestIndex = index;
        if (leftIndex < maxIndex && arr[leftIndex] > arr[index]) {
            largestIndex = leftIndex;
        }

        if (rightIndex < maxIndex  && arr[rightIndex] > arr[largestIndex]) {
            largestIndex = rightIndex;
        }

        if (largestIndex != index) {
            int tmp = arr[index];
            arr[index] = arr[largestIndex];
            arr[largestIndex] = tmp;
            heapify(arr, largestIndex, maxIndex);
        }

        return arr;
    }
}