【データ構造とアルゴリズム】最小スタックminheap

最小スタックは最大スタック実現構想と同様であるが,順序が異なるだけで,ここでは最小スタックのみを記録する.
最小スタックの定義は、各ノードが親ノード以上である完全な二叉木です.完全に二叉樹は葉が最後の層にあり、できるだけ左に寄る.
インプリメンテーションでは、チェーンテーブルまたは配列を使用できます.ここでは配列を使用します.
配列を使用する場合、下付き文字は0から始まり、親ノードはiであり、左サブツリーは2*i+1、右サブツリーは2*i+2である.子ノードがiの場合、親ノードは(i-1)/2です.
minheapの操作は主に2つあり、1つはaddであり、最後にノードを新規作成し、親ノードと絶えず比較し、親ノードより小さい場合は、等しいかrootより大きいまで交換することを考えています.
2つ目の操作はrootを出力することです.最後のノードをroot位置に移動し、minheapを再整理する必要があります.この場合、minheapがshiminheapされなくなる可能性があります.整理プロセスは関数minheapifyで実現されます.この関数の実現構想は,iをルートとするサブツリーが整理される必要があることを示し,iとiより小さいサブノードの小さな値を交換し,交換されたノードを再帰的に整理することである.
次はコードです.ここでは、配列のサイズや空のheapを出力する場合など、境界は考慮されていません.

public class MinHeap {

	private int size = 0;
	private int[] heap = new int[100];
	
	public void add(int data){
		heap[size++] = data;
		int i = size - 1;
		while(i > 0 && heap[i] < heap[(i - 1) / 2]){
			swap(i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}
	
	public int top(){
		size --;
		int r = heap[0];
		swap(size, 0);
		minheapify(0);
		return r;
	}
	
	public void minheapify(int i){
		int l = 2 * i + 1;
		int r = 2 * i + 2;
		int small = i;
		if(l < size && heap[i] > heap[l]){
			small = l;
		}
		if(r < size && heap[r] < heap[small]){
			small = r;
		}
		if(i != small){
			swap(i, small);
			minheapify(small);
		}
	}
	
	private void swap(int i, int j){
		int temp = heap[i];
		heap[i] = heap[j];
		heap[j]= temp;
	}
	
	public int size(){
		return size;
	}
}