基本ヒープソート

一、概念とその紹介

ヒープソート(Heapsort)は、ヒープというデータ構造を利用して設計されたソートアルゴリズムです。

ヒープは、ほぼ完全二分木の構造であり、同時にヒープの性質を満たします:すなわち、子ノードのキー値またはインデックスは、常にその親ノードより小さい(または大きい)ことです。

二、適用説明

以前のヒープ構築プロセスは、データごとに insert メソッドを呼び出し、shift up を使用して一つずつヒープに挿入するというものでした。このアルゴリズムの時間計算量はO(nlogn)、本節で紹介するヒープソートを構築するプロセスは、と呼ばれますHeapify、アルゴリズムの時間計算量はO(n)。

三、プロセス図示

完全二分木には重要な性質があります。最初の非葉ノードのインデックスはn/2整数として取得したインデックス値です。ここでnは要素数です(前提として、配列インデックスは 1 から始まるものとします)。

インデックス 5 の位置が最初の非葉ノードです。そこから前へ順に、各要素をそれぞれルートノードとして shift down 操作を行い、最大ヒープの性質を満たします。

インデックス 5 の位置で shift down 操作を行った後、22 と 62 の位置を交換します。

インデックス 4 の要素に対して shift down 操作を行います

インデックス 3 の要素に対して shift down 操作を行います

インデックス 2 の要素に対して shift down 操作を行います

最後にルートノードに対して shift down 操作を行うと、ヒープソートのプロセス全体が完了します。

四、Java サンプルコード

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

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

package サンプル.heap;

import サンプル.sort.SortTestHelper;

/**
* heapify を使用してヒープソートを行う
 */

public class Heapify<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // コンストラクタ。与えられた配列から最大ヒープを作成します
    // このヒープ構築プロセスの時間計算量は O(n) です
    public Heapify(T arr[]){

        int n = arr.length;

        data = (T[])new Comparable[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;
        // 最初の非葉ノードの要素から開始します
        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }
    // ヒープ内の要素数を返します
    public int size(){
        return count;
    }
    // ヒープが空かどうかを示すブール値を返します
    public boolean isEmpty(){
        return count == 0;
    }
    // 最大ヒープに新しい要素 item を挿入します
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // 最大ヒープからヒープの先頭要素を取り出します。つまり、ヒープに格納されている最大データです
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // 最大ヒープの先頭要素を取得します
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }


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

    //********************
    //* 最大ヒープの中核となる補助関数
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    private void shiftDown(int k){

        while( 2*k <= count ){
            int j = 2*k; // このループでは、data[k] と data[j] が位置を交換します
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
                j ++;
            // data[j] は data[2*k] と data[2*k+1] のうちの最大値です

            if( data[k].compareTo(data[j]) >= 0 ) break;
            swap(k, j);
            k = j;
        }
    }

    // heapify をテストします
    public static void main(String[] args) {
        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        Heapify<Integer> heapify = new Heapify<Integer>(arr);
        // heapify 内のデータを extractMax を使用して徐々に取り出します
        // 取り出される順序は、大きい順(降順)でなければなりません
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapify.extractMax();
            System.out.print(arr[i] + " ");
        }

        // arr 配列が降順(大きい順)に並んでいることを確認します
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }
}
その他の拡張