ヒープの 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];
}
}
/**
* 最大ヒープから要素を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];
}
}