downheap()

前節の配列表現を使って, 2 分木の任意の位置から要素を落す関数 downheap() を書いてみる.

def downheap(A,K,N) {
    /* place A[K] at the correct position in A */
    while ( 2*K <= N ) {
        J = 2*K;  /* A[J] is the first child */
        if ( J == N ) {
            /* A[J] is the unique child */
            if ( A[K] < A[J] ) swap(A,K,J);
            /* A[J] is a leaf */
            break;
        } else {
            /* A[K] has two children A[J] and A[J+1] */
            /* M = max(A[K],A[J],A[J+1]) */
            M = A[K] >= A[J] ? A[K] : A[J];
            if ( A[J+1] > M ) M = A[J+1];

            if ( M == A[K] ) break; /* we have nothing to do */
            else if ( M == A[J] ) {
                swap(A,K,J);
                K = J; /* A[K] is moved to A[J]; */
            } else {
                swap(A,K,J+1);
                K = J+1; /* A[K] is moved to A[J+1]; */
            }
        }
    }
}

def swap(A,I,J) {
    T = A[I]; A[I] = A[J]; A[J] = T;
}

これは, 次のように簡潔に書ける.

def downheap(A,K,N) {
    V = A[K];
    while ( 2*K <= N ) {
        J = 2*K;
        if ( J < N && A[J] < A[J+1] ) J++;
        if ( V >= A[J] ) break;
        else {
            A[K] = A[J];
            K = J;
        }
    }
    A[K] = V;
}

問題 13.3   このプログラムの動作を説明せよ.

問題 13.4   上から落して正しい位置に置くのが downheap() だが, 葉としてつけ加え て, 親より大きかったら親と交換する, という方法で昇らせることでもヒープが 再構成できる. この関数 upheap(A,K) を書け.