ヒープのshift up

本節では、最大ヒープに要素を追加する方法を紹介します。これをshift up。

下の最大ヒープに新しい要素52を追加し、配列の最後の位置に置くとします。52は親ノード16より大きいため、この時点でヒープの定義を満たしておらず、調整が必要です。

まず、インデックス5と11の配列内の数値の位置を交換します。つまり、52と16の位置を交換します。

この時、52は依然として親ノードのインデックス2の値41より大きいため、さらに位置を移動する必要があります。

ここで52と62の大小を比較すると、52はすでに親ノードより小さいため、これ以上上昇させる必要はなく、最大ヒープの定義を満たしています。このプロセスを最大ヒープのshift upと呼びます。

Java インスタンスコード

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

src/サンプル/heap/HeapShiftUp.java ファイルコード：

package サンプル.heap;

/**
* ヒープに要素を追加する
 */
public class HeapShiftUp<T extends Comparable> {

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

    // コンストラクタ。capacity個の要素を格納できる空のヒープを構築する
    public HeapShiftUp(int 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);
    }
    // ヒープ内のインデックス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;
        }
    }

    // HeapShiftUp をテストする
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // ヒープ内の要素数
        int M = 100; // ヒープ内の要素の値の範囲は[0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
その他の拡張