前節の配列表現を使って, 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; }