ヒープの shift down

この小節では、最大ヒープから要素を1つ取り出す方法を紹介します。これを shift down と呼びます。最大優先度の要素、つまりルートノードのみを取り出すことができます。元の 62 を取り出した後、この最大ヒープをどのように埋めるかを以下で紹介します。

第一步として、配列の最後の要素をルートノードに置きます。このとき、最大ヒープの定義を満たしていません。

調整のプロセスは、このルートノード 16 を一歩ずつ下へ移動させることです。16 は子ノードより小さいので、まず子ノード 52 と 30 のどちらが大きいかを比較し、大きい方と位置を交換します。

続けて 16 の子ノード 28 と 41 を比較すると、41 が大きいので、16 と 41 の位置を交換します。

さらに 16 と子ノード 15 を比較すると、16 の方が大きいため、交換は必要ありません。これで shift down 操作が完了し、最大ヒープの性質が維持されました。

四、Java インスタンスコード

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

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

package サンプル.heap;

/**
* 最大ヒープから要素を1つ取り出す
 */

public class HeapShiftDown<T extends Comparable> {

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

    // コンストラクタ。空のヒープを構築し、capacity個の要素を格納できる
    public HeapShiftDown(int capacity){
        // ここで1を加えるのは、元々格納できる要素の個数を指している。0番目の位置を除くと、capacity個の要素しか格納できない
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // ヒープ内の要素数を返す
    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;
        }
    }
    //shiftDown操作
    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;
        }
        System.out.println("shiftDown終了");
    }

    // HeapShiftDown をテストする
    public static void main(String[] args) {
        HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
        // ヒープ内の要素数
        int N = 100;
        // ヒープ内の要素の値の範囲は[0, M)
        int M = 100;
        for( int i = 0 ; i < N ; i ++ )
            heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
        Integer[] arr = new Integer[N];
        // 最大ヒープ内のデータを徐々に extractMax を使用して取り出す
        // 取り出される順序は、大きいものから小さいものへの順序であるべきです
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapShiftDown.extractMax();
            System.out.print(arr[i] + " ");
        }
        // arr配列が大きいものから小さいものへ並んでいることを確認する
        for( int i = 1 ; i < N ; i ++ )
            assert arr[i-1] >= arr[i];
    }
}
その他の拡張