import java.util.*;
//A simple priority queue impelemented by heap

public class PriorityQueue {
	private Vector<Node> node_queue;
	public PriorityQueue() {
		node_queue = new Vector<Node>();
	}
	private void upHeap(int ci) {
		if (ci == 0) return;//reach root
		int pi = (ci - 1) / 2;

		Node childPuzzle = node_queue.elementAt(ci);
		Node parentPuzzle = node_queue.elementAt(pi);
		if (childPuzzle.getCost()<parentPuzzle.getCost()) {
			node_queue.setElementAt(parentPuzzle, ci);
			node_queue.setElementAt(childPuzzle, pi);
			upHeap(pi);
		}
	}
	private void downHeap(int pi) {
		int ci = (2 * pi) + 1;
		if (ci >= node_queue.size()) return;//reach root
		Node childPuzzle = node_queue.elementAt(ci);
		if (ci + 1 < node_queue.size()) {
			Node rightPuzzle = node_queue.elementAt(ci + 1);
			if (rightPuzzle.getCost()< childPuzzle.getCost() ) {
				childPuzzle = rightPuzzle;
				ci++;
			}
		}
		Node parentPuzzle = node_queue.elementAt(pi);
		if (childPuzzle.getCost()<parentPuzzle.getCost() ) {
			node_queue.setElementAt(parentPuzzle, ci);
			node_queue.setElementAt(childPuzzle, pi);
			downHeap(ci);
		}
	}

	public void addElement(Node n) {
		node_queue.addElement(n);
		upHeap(node_queue.size() - 1);
	}
	public boolean hasMoreElements() {
		return (node_queue.size() > 0);
	}
	public Node removeElement() throws ArrayIndexOutOfBoundsException {
		Node topNode = node_queue.elementAt(0);
		Node lastNode = node_queue.elementAt(node_queue.size() - 1);
		node_queue.removeElementAt(node_queue.size() - 1);

		if (node_queue.size() > 0) {
			node_queue.setElementAt(lastNode, 0);
			downHeap(0);
		}
		return topNode;
	}
}