import java.awt.*;
import java.awt.event.*;

class BinaryHeap 
{
	private Node[] heapArray;
	
	private int maxSize;
	private int currentSize;
	private int[] pos;
	
	public BinaryHeap(int mx)
	{
		maxSize=mx;
		currentSize=0;
		heapArray=new Node[maxSize];
		pos=new int[maxSize];
	}
	
	public boolean isEmpty()
	{
		return currentSize==0;
	}
	
	public boolean insert(Node n)
	{
		if(currentSize==maxSize)
			return false;
		Node newNode=n;
		
		heapArray[currentSize]=newNode;
		pos[newNode.nodeid]=currentSize;
		trickleUp(currentSize++);
		return true;
	}
	
	public void trickleUp(int index)
	{
		int parent=(index-1) /2;
		Node bottom=heapArray[index];
		while(index  > 0 && heapArray[parent].returnkey() >  bottom.returnkey())
		{
			heapArray[index]=heapArray[parent];
			pos[heapArray[index].nodeid]=index;
			index=parent;
			parent=(parent-1)/2;
		}
		heapArray[index]=bottom;
		pos[bottom.nodeid]=index;
		

	}
	
	
	public Node deleteMin()
	{
		Node root=heapArray[0];
		heapArray[0]=heapArray[--currentSize];
		pos[heapArray[0].nodeid]=0;
		trickleDown(0);
		return root;
	}
	
	public Node returnMin()
	{
		return heapArray[currentSize-1];
	}
	
	public void trickleDown(int index)
	{
		int largerChild;
		Node top=heapArray[index];
		while(index < currentSize/2)
		{
			int leftChild=2*index+1;
			int rightChild=leftChild+1;
			if(rightChild<currentSize && heapArray[leftChild].returnkey() > heapArray[rightChild].returnkey())
				largerChild=rightChild;
			else
				largerChild=leftChild;
			if(top.returnkey() <= heapArray[largerChild].returnkey())
				break;
				
			heapArray[index]=heapArray[largerChild];
			pos[heapArray[index].nodeid]=index;
			index= largerChild;
		}
		heapArray[index]=top;
		pos[top.nodeid]=index;
	}
	
	
	public boolean decreaseKey(int nodeid , int val)
	{
		int index=pos[nodeid];
		if(index<0 || index>=currentSize)
			return false;
		if(heapArray[index].returnkey()< val )
			return false;
		
		heapArray[index].key=val;
		trickleUp(index);
		
		return true;
	}
	
	public Node returnNode(int nodeid)
	{
		return heapArray[pos[nodeid]];
	}
	
	
	
	
}