データ構造とアルゴリズム08のスタック

優先キューは、最大データ項目を削除する時間の複雑さがO(1)であるにもかかわらず、挿入には長いO(N)時間が必要であるという問題があります.これは、配列の平均半分のデータ項目を移動して新しいデータ項目を挿入し、挿入が完了した後も配列が秩序化されているためです.
優先順位キューを実装する別の構造:スタックについて説明します.スタックはjavaやC++などのコンパイル言語の「スタック」ではないツリーです.これにより実現される優先キューの挿入と削除の時間的複雑さはいずれもO(logn)である.このように削除する時間は少し遅くなりましたが、挿入する時間はずっと速くなりました.速度が非常に重要であり、多くの挿入操作がある場合、優先キューを実装するためにスタックを選択することができます.スタックには次のような特徴があります.
・完全二叉木です.すなわち,木の最後の層ノードが満である必要がない以外は,左から右まで完全に満である.
・配列で実装されることが多い.配列で実現される完全なツリーでは、ノードのインデックスには次のような特徴があります(ノードのインデックスをxとします).
親ノードのインデックスは(x-1)/2です.
その左サブノードインデックスは2*x+1です.
右サブノードインデックスは2*x+2です.
・スタック内の各ノードのキーワードは、このノードのサブノードのキーワードよりも大きい(または等しい).これも、スタック内の各ノードが満たさなければならない条件である.したがって、スタックは二叉探索ツリーに比べて弱いシーケンスである.
スタックにデータを挿入し、まずリーフノード(配列の最後のアイテム)にデータアイテムを格納し、そのノードからスタック内のノードキーの条件を満たすまで段階的に調整します.
スタックからデータを削除するのは挿入とは異なり、削除時にルートノードのデータは永遠に削除されます.ルートノードのデータが最大であるため、削除が完了したら、最後のリーフノードをルートの位置に移動し、ルートから、スタック内のノードキーのエントリを満たすまで段階的に下に調整します.具体的には、次のコードを参照してください.

public class Heap {
	
	private Node[] heapArray;
	private int maxSize;
	private int currentSize;
	
	public Heap(int mx) {
		maxSize = mx;
		currentSize = 0;
		heapArray = new Node[maxSize];
	}
	
	public boolean isEmpty() {
		return (currentSize == 0)? true : false;
	}
	
	public boolean isFull() {
		return (currentSize == maxSize)? true : false;
	}
	
	public boolean insert(int key) {
		if(isFull()) {
			return false;
		}
		Node newNode = new Node(key);
		heapArray[currentSize] = newNode;
		trickleUp(currentSize++);
		return true;
	}
	//    
	public void trickleUp(int index) {
		int parent = (index - 1) / 2; //      
		Node bottom = heapArray[index]; //         bottom 
		while(index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
			heapArray[index] = heapArray[parent];
			index = parent;
			parent = (parent - 1) / 2;
		}
		heapArray[index] = bottom;
	}
	
	public Node remove() {
		Node root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}
	//    
	public void trickleDown(int index) {
		Node top = heapArray[index];
		int largeChildIndex;
		while(index < currentSize/2) { //while node has at least one child
			int leftChildIndex = 2 * index + 1;
			int rightChildIndex = leftChildIndex + 1;
			//find larger child
			if(rightChildIndex < currentSize &&  //rightChild exists?
					heapArray[leftChildIndex].getKey() < heapArray[rightChildIndex].getKey()) {
				largeChildIndex = rightChildIndex;
			}
			else {
				largeChildIndex = leftChildIndex;
			}
			if(top.getKey() >= heapArray[largeChildIndex].getKey()) {
				break;
			}
			heapArray[index] = heapArray[largeChildIndex];
			index = largeChildIndex;
		}
		heapArray[index] = top;
	}
	//            
	public boolean change(int index, int newValue) {
		if(index < 0 || index >= currentSize) {
			return false;
		}
		int oldValue = heapArray[index].getKey();
		heapArray[index].setKey(newValue);
		if(oldValue < newValue) {
			trickleUp(index);
		}
		else {
			trickleDown(index);
		}
		return true;
	}
	
	public void displayHeap() {
		System.out.println("heapArray(array format): ");
		for(int i = 0; i < currentSize; i++) {
			if(heapArray[i] != null) {
				System.out.print(heapArray[i].getKey() + " ");
			}
			else {
				System.out.print("--");
			}
		}
	}
}
class Node {
	private int iData;
	public Node(int key) {
		iData = key;
	}
	
	public int getKey() {
		return iData;
	}
	
	public void setKey(int key) {
		iData = key;
	}
}