6-8 ヒープソート

ヒープ

親の値が子の値以上である、完全2分木のこと
兄弟での大小関係は任意
- ヒープのことを別名、半順序木 partial ordered tree ともいう
a[i] に対して、
- 親は　a[(i - 1) / 2]
- 左の子は　a[i * 2 + 1]　※剰余切り捨て
- 右の子は　a[i * 2 + 2]

根を削除したヒープの再構築

根を取り出す
最後の要素(最下流の最も右側に位置する要素)を根に移動する
自分より大きい方の子と交換して一つ下流に降りる作業を、根から始めて、以下の条件何れかが成立するまで繰り返す
- 子の方が値が小さい
- 葉に到達した

ヒープソートへの拡張

変数 i の値を n - 1 で初期化する
a[0] と a[i] を交換する
a[0], a[1], …, a[i - 1] をヒープ化する
i の値をデクリメントして 0 になれば終了
そうでなければ2に戻る

配列のヒープ化

ソースコード

import java.util.Scanner;

class HeapSort {
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void downHeap(int[] a, int left, int right) {
        int temp = a[left];
        int child;
        int parent;

        for (parent = left; parent < (right + 1) / 2; parent = child) {
            int cl = parent * 2 + 1;
            int cr = cl + 1;
            child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
            if (temp >= a[child]) {
                break;
            }
            a[parent] = a[child];
        }
        a[parent] = temp;
    }

    static void heapSort(int[] a, int n) {
        for (int i = (n - 1) / 2; i >= 0; i--) {
            downHeap(a, i, n - 1);
        }

        for (int i = n - 1; i > 0; i--) {
            swap(a, 0, i);
            downHeap(a, 0, i - 1);
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("ヒープソート");
        System.out.print("要素数: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = stdIn.nextInt();
        }

        heapSort(x, nx);

        System.out.println("昇順にソートしました。");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "]: " + x[i]);
        }
    }
}

ちょい飽きたので飛ばし