import java.util.*;
/**
  * A speedy implementation of the Heap using
  * an array.  Within the array, there is a null element at index 0,
  * the root of the tree at index 1, and the rest of the tree is
  * contained as follows.  If node n has index i,
  * then the left child of n will have index 2*i,
  * and the right child of n will have index 2*i +
  * 1.  Traversing the contents of the array in order of increasing
  * index yields a level-order traversal
  *
  * @author Yong Yang
  */
  
    /** ArrayNode class for MyHeap. */
 class ArrayNode {
    double key;
    String value; // value stored at this position
    public ArrayNode(){
    	key=0;
    	value = null;
    }
    public ArrayNode(double k, String elt) {
      key = k;
      value = elt;
    }
    public ArrayNode(ArrayNode temp){
    	this.key = temp.key;
    	this.value = temp.value;
    }
    public double key() { return key;  }
    public String value() { return value; }
    public double setKey(double k){
    	double temp = key;
    	key = k;
    	return temp;
    }
    public String setValue(String elt) {
      String temp = value;
      value = elt;
      return temp;
    }
  }  
  
  
  
public class MyHeap{
  
  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
  
  
  /** default constructor */
  public MyHeap() { 
    T = new ArrayNode[1001]; // default maximum number of entries is 1000
    T[0]=new ArrayNode(0.0d, null); // the location at index 0 is deliberately empty
    maxEntries=1000;
    numEntries=0;
  }
  
  public MyHeap(int max) {
	T = new ArrayNode[max+1];
    T[0]=new ArrayNode(0.0d,null); // the location at index 0 is deliberately empty
    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 and value x */
  public void insert(double k, String x) {
  	if(numEntries<maxEntries){
  		numEntries++;
  		T[numEntries] = new ArrayNode(k,x);
  		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]);
  		if(numEntries==1) {
  			T[1].setKey(0.0d);
  			T[1].setValue(null);
  			numEntries--;
  		}
  		else{
  			T[1].setKey(T[numEntries].key);
  			T[1].setValue(T[numEntries].value);
  			T[numEntries].setKey(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].setValue(T[j].value);
    T[j].setKey(vv.key);
    T[j].setValue(vv.value);
  }

  
  /** 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].value+"}");  	 
  	}
  	}
  }

  public static void main(String[] args){
  	int max,n;
  	double k;
  	String obj;
  	
  	System.out.println("please input the maximum number of entries in the heap");
  	Scanner sc = new Scanner(System.in);
  	max = sc.nextInt();
  	MyHeap tr= new MyHeap(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+"th node");
  			k = sc.nextDouble();
  			System.out.println("Please input the value of the " + i + "th node");
  			obj = sc.next();
  			tr.insert(k,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();
  }

}