package Asg2;
import java.util.*;

/** ArrayNode class for MyHeap. */
class ArrayNode {
	int key;
	char letter; // value stored at this position
	ArrayNode parent;
	ArrayNode left;
	ArrayNode right;
	String huffmanCode = ""; //used to get the Huffman code for the HuffmanTree.java
    
	public ArrayNode(){
    	key=0;
    	letter = '\0';
    	parent = null;
    	left = null;
    	right = null;
    }
	
	public ArrayNode(int k, char elt) {
		key = k;
		letter = elt;
		this.parent = null;
		this.left = null;
		this.right = null;
	}
    
	public ArrayNode(int k, char elt, ArrayNode parent, 
			ArrayNode left, ArrayNode right) {
		key = k;
		letter = elt;
		this.parent = parent;
		this.left = left;
		this.right = right;
    }
    
	public ArrayNode(ArrayNode temp){
    	this.key = temp.key;
    	this.letter = temp.letter;
    	this.parent = temp.parent;
    	this.left = temp.left;
    	this.right = temp.right;
    }
    
	public int key() { return key;  }
    
	public char value() { return letter; }
    
	public ArrayNode parent() { return parent; }
	
	public ArrayNode left() { return left; }
	
	public ArrayNode right() { return right; }
	
	public String huffmanCode() { return huffmanCode; }
	
	public double setKey(int k){
    	double temp = key;
    	key = k;
    	return temp;
    }
    
	public char setValue(char elt) {
      char temp = letter;
      letter = elt;
      return temp;
    }
	
	public void setParent(ArrayNode parent) {
		this.parent = parent;
	}
	
	public void setLeft(ArrayNode left) {
		this.left = left;
	}
	
	public void setRight(ArrayNode right) {
		this.right = right;
	}
	
	public void setHuffmanCode(String str) {
		this.huffmanCode = str;  
	}
 }  
  
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, '\0'); // 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, '\0'); // 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(int k, char 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;
  		}
	}
	
	/** inserts an entry with ArrayNode */
	public void insert(ArrayNode node) {
		if(numEntries<maxEntries){
			numEntries++;
			T[numEntries] = node;
			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);
				T[1].setValue('\0');
				numEntries--;
			}
			else{
				T[1].setKey(T[numEntries].key);
				T[1].setValue(T[numEntries].letter);
				T[1].setLeft(T[numEntries].left());
				T[1].setRight(T[numEntries].right());
				T[1].setParent(T[numEntries].parent());
				T[numEntries].setKey(0);
				T[numEntries].setValue('\0');
				T[numEntries].setLeft(null);
				T[numEntries].setRight(null);
				T[numEntries].setParent(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].letter);
		T[i].setLeft(T[j].left());
		T[i].setRight(T[j].right());
		T[i].setParent(T[i].parent());
		
		T[j].setKey(vv.key);
		T[j].setValue(vv.letter);
		T[j].setLeft(vv.left());
		T[j].setRight(vv.right());
		T[j].setParent(vv.parent());
	}

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

  	public static void main(String[] args){
  		Scanner input = new Scanner(System.in);
  		System.out.println("please input the maximum number of entries in a heap");
  		int maxNum = input.nextInt();
  		System.out.println("please input the number of entries in a heap");
  		int numElt = input.nextInt();
  		MyHeap myheap = new MyHeap(maxNum);
  		
  		for (int i = 0; i < numElt; i++) {
  			int frequency = input.nextInt();
  			char character = input.next().charAt(0);
  			myheap.insert(frequency, character);
  		}
  		for (int i = 0; i < numElt; i++)
  			System.out.println(myheap.min().key+" "+myheap.removeMin().letter);
  	
  		input.close();
  	}
}