import java.util.Scanner;


class ArrayNode {
    double key;
    int id; // identificsation of the entry id=1,2, 3, ? n
    String value; // value stored at this position

	public ArrayNode(double k, int d, String elt) {
		key = k;
		id = d;
		value = elt;
	}

	public ArrayNode(ArrayNode temp) {
		this.key = temp.key;
		this.id = temp.id;
		this.value = temp.value;
	}

	public double key() {
		return key;
	}
	
	public double id() {
		return id;
	}

	public String value() {
		return value;
	}

	public double setKey(double k) {
		double temp = key;
		key = k;
		return temp;
	}
	
	public int setId(int d) {
		int temp = id;
		id = d;
		return temp;
	}

	public String setValue(String elt) {
		String temp = value;
		value = elt;
		return temp;
	}
}

public class MyAdaptableHeap {

	protected ArrayNode T[];  // array of elements stored in the tree
	protected int maxEntries; // maximum number of entries
	protected int numEntries; //num of entries in the heap
	protected int location[]; 

	/** default constructor */
	public MyAdaptableHeap() {
		T = new ArrayNode[1001]; // default maximum number of entries is 1000
		T[0] = new ArrayNode(0.0d, 0,null); // the location at index 0 is
		location = new int[1001];                                  // deliberately empty
		for(int i = 0; i < 1001; i++){
			location[i] = i;
		}
		
		maxEntries = 1000;
		numEntries = 0;
	}

	public MyAdaptableHeap(int max) {
		T = new ArrayNode[max + 1];
		T[0] = new ArrayNode(0.0d, 0, null); // the location at index 0 is
		location = new int[max+1];									// deliberately empty
		for(int i = 0; i < max+1; i++){
			location[i] = i;
		}
		
		maxEntries = max;
		numEntries = 0;
	}
	
	/** Returns the number of (internal and external) nodes. */
	public int size() {
		return numEntries;
	}

	/** Returns whether the tree is empty. */
	public boolean isEmpty() {
		return (size() == 0);
	}

	/** Returns the root of the tree. */
	public ArrayNode min() {
		if (isEmpty()) {
			System.out.println("Nothing Return!!! The heap is empty");
			return null;
		}
		return T[1];
	}

	/** inserts an entry with key k, id d, and value x */
	public void insert(double k, int d, String x) {
		if (numEntries < maxEntries) {			 
			numEntries++;			 
			T[numEntries] = new ArrayNode(k, d, x);
			location[d] = numEntries;
			int parent = numEntries / 2;
			int child = numEntries;
			while (parent >= 1) {
				if (T[parent].key > T[child].key) {
					swapElements(parent, child);
					child = parent;
					parent = parent / 2;
				} else
					break;
			}
		} else {
			System.out.println("Insert failure!!! Heap is full");
			return;
		}
	}

	public ArrayNode removeMin() {
		if (isEmpty()) {
			System.out.println("Remove failure!!! Heap is empty");
			return null;
		} else {
			ArrayNode temp = new ArrayNode(T[1]);
			int d = T[1].id;
			if (numEntries == 1) {
				T[1].setKey(0.0d);
				T[1].setId(0);
				T[1].setValue(null);
				location[1] = 0;
				numEntries--;
			} else {
				location[d] = 0;
				T[1].setKey(T[numEntries].key);
				T[1].setId(T[numEntries].id);
				T[1].setValue(T[numEntries].value);
				T[numEntries].setKey(0);
				T[numEntries].setId(0);
				T[numEntries].setValue(null);
				numEntries--;

				int parent = 1, left = 2, right = 3;
				while (left <= numEntries) {
					if (right <= numEntries) {
						if (T[parent].key > T[left].key
								|| T[parent].key > T[right].key) {
							if (T[left].key <= T[right].key) {
								swapElements(parent, left);
								parent = left;
								left = 2 * parent;
								right = left + 1;
							} else {
								swapElements(parent, right);
								parent = right;
								left = 2 * parent;
								right = left + 1;
							}

						} else
							break;
					} else {
						if (T[parent].key > T[left].key)
							swapElements(parent, left);
						break;
					}
				}
			}
			return temp;
		}
	}

	/** Swaps two nodes. */
	public void swapElements(int i, int j) {
		ArrayNode vv = new ArrayNode(T[i]);
		T[i].setKey(T[j].key);
		T[i].setId(T[j].id);
		T[i].setValue(T[j].value);
		location[T[i].id] = i;
		T[j].setKey(vv.key);
		T[j].setId(vv.id);
		T[j].setValue(vv.value);
		location[T[j].id] = j;
	}

	/** display the tree */
	public void display() {
		if (isEmpty())
			System.out.println("The heap is empty");
		else {
			for (int i = 1; i <= numEntries; i++) {			 
					System.out.println("The " + i + "st node:{" + T[i].key
							+ ", " + T[i].id + ", " + T[i].value + "}");				 
			}
		}
	}

	//replace the key of the node with id=id to be k
	public void replace(int id, double k){
		int rank = location[id];
		System.out.println("rank="+rank);
		if(rank != 0){
			replaceKey(rank,k);
		}
		else
			System.out.println("the node with id="+id+"does not exist");
	}
	
	
	//replace the key of the i th node to be k 
	public void replaceKey(int i, double k) {
		double originalKey = T[i].key();
		T[i].setKey(k);
		double temp = 0;
		int tempIndex = 0;

		 
		
		if (k == originalKey)
			return ;
		else if (k < originalKey) {
		 
			while (i > 1) { // check for the upheap operation
				if (T[i].key() < T[i / 2].key()) {
					swapElements(i,i/2);
					i = i / 2;

				} else
					break;
			}
		} 
		else {
			 
			while (2 * i <= numEntries) { // check for the downheap operation
				tempIndex = 2 * i; // tempIndex: the index of child node with smaller value
				if (2 * i + 1 <= numEntries) {
					if (T[2 * i].key() > T[2 * i + 1].key()) {
						tempIndex = 2 * i + 1;
					}
				}
				System.out.println("tempIndex ="+tempIndex );
				if (T[i].key() > T[tempIndex].key()) {
					swapElements(i,tempIndex);
					i = tempIndex;
				}
				else
					break;

			}
		}
	}

	
	public static void main(String[] args) {
		int max, n;
		double k;
		int id;
		String obj;

		System.out
				.println("please input the maximum number of entries in the heap");
		Scanner sc = new Scanner(System.in);
		max = sc.nextInt();
		MyAdaptableHeap tr = new MyAdaptableHeap(max);	
		
	
		System.out
				.println("Please input the number of entries in the heap which you want to  creat");
		n = sc.nextInt();

		/** construct the heap and diplay the current heap */
		for (int i = 1; i <= n; i++) {
			 
				System.out.println("Please input the key of the " + i
						+ "st node");
				k = sc.nextDouble();
				System.out.println("Please input the id of the " + i
						+ "st node");
				id = sc.nextInt();
				System.out.println("Please input the value of the " + i
						+ "st node");
				obj = sc.next();
				tr.insert(k, id, obj);
		 
			System.out.println("The current heap is:");
			tr.display();
		}

		/** test the method removeMin() */
		System.out
				.println("Now, we remove the nodes one by one, and display the result");
		while (tr.numEntries > 0) {
			System.out.println("Remove a node");
			tr.removeMin();
			System.out.println("The current heap is: ");
			tr.display();			 
		}

		/** just for test the exception of removeMin() */
		System.out.println("Remove a node");
		tr.removeMin();
		System.out.println("The currenet heap is: ");
		tr.display();
		
		tr = new MyAdaptableHeap(max);
		tr.insert(11, 6, "a");
		tr.insert(12, 7, "b");
		tr.insert(13, 4, "c");
		tr.insert(14, 1, "d");
		tr.insert(15, 3, "e");
		tr.insert(16, 2, "f");
		tr.insert(17, 5, "g");
		tr.display();
		tr.replace(4, 25);
		tr.display();
		tr.replace(7, 1);
		tr.display();
	}
}