import java.util.*;
import java.awt.*;
import java.text.*;

public class BinaryHeap {

	int [] dataArray;   // Array to store heap elements
	int numData;        // Number of nodes in the heap
	int maxSize = 32;   // Size of dataArray
	
	public void percolateUp(int nodeIndex)
	{
		int nodeData = dataArray[nodeIndex];
		int index = nodeIndex;
		
		while( true ){
			int parent = index/2;
			/*
			 *   Determine if the current node has a valid parent (i.e. parent >= 1) 
			 *   and parent's node value is larger than nodeData, 
			 *   	assign parent's node value to current node
			 *   	assign parent index to current 'index'.
			 *  else
			 *  	break the while loop
			 */
			
			if( parent >= 1  && dataArray[parent] > nodeData ){
				dataArray[index] = dataArray[parent];
				index = parent;
			} else
				break;
		}
		dataArray[index] = nodeData;
	}
	
	public void percolateDown(int nodeIndex)
	{
		int nodeData = dataArray[nodeIndex];
		int index = nodeIndex;
		while( true )
		{
			int leftChild = 2*index;
			int rightChild = 2*index + 1;
			int smallerChild = 0;
			
			/* 
			 *  Determine which of lefChild and rightChild has smaller node value, 
			 *   ( call it smallerChild ). 
			 *  NOTE: 
			 *  (a) Need to confirm each of the children is valid (i.e. <= numData).
			 *  (b) If only leftChild is valid than it is the smaller child.
			 *  (c) If both children are invalid then break the while loop.
			 */
			if( rightChild <= numData )
			{
				if( dataArray[leftChild] < dataArray[rightChild] )
					smallerChild = leftChild;
				else
					smallerChild = rightChild;
			}
			else if ( leftChild <= numData )
					smallerChild = leftChild;
			else
				break;
			/*
			 *  If node value of the smallerChild is lesser than nodeData, then 
			 *  	assign smallerChild node value to the current node (i.e. node at 'index').
			 *   	update index to smallerChild index.
			 *  
			 *  Otherwise, break the while loop.
			 */
			if( dataArray[smallerChild] < nodeData )
			{
				dataArray[index] = dataArray[smallerChild];
				index = smallerChild;
			}
			else
				break;
		}
		dataArray[index] = nodeData;
	}
	
	public void insert(int newValue)
	{
		if( numData == maxSize-1 )
		{
			int [] newDataArray = new int[2*maxSize];
			for(int i = 0; i < maxSize; i++)
				newDataArray[i] = dataArray[i];
			maxSize = 2*maxSize;
			dataArray = newDataArray;
		}
		numData++;
		dataArray[numData] = newValue;
		percolateUp(numData);
	}
	
	public int deleteMin()
	{
		if( numData < 1 )
			return -1;
		int minValue = dataArray[1];
		dataArray[1] = dataArray[numData];
		numData--;
		percolateDown(1);
		return minValue;
	}
	
	public boolean checkHeapProperty(int nodeIndex){
		if( nodeIndex < 1 || nodeIndex > numData )
			return false;
		int nodeData = dataArray[nodeIndex];
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.offer(nodeIndex);
		while(!queue.isEmpty())
		{
			int childIndex = queue.remove().intValue();
			if( dataArray[childIndex] < nodeData )
				return false;
			if( 2*childIndex <= numData )
				queue.offer(2*childIndex);
			if( 2*childIndex + 1 <= numData )
				queue.offer(2*childIndex + 1);	
		}
		return true;
	}
	
	public int getNumLevels(){
		return (int)Math.ceil(Math.log(numData) / 0.6931471806);
	}
	
	int node_diameter = 40;
	Point [] node_coordinates;
	
	public int getNodeIndexMouseClick( Point clickPoint )
	{
		int radius = node_diameter / 2;
		for(int i = 1; i <= numData; i++)
		{
			Point pt = node_coordinates[i];
			if( clickPoint.distance(pt.x + radius, pt.y + radius) < radius )
				return i;
		}
		return -1;
	}
	
	public void addGraphics(Graphics g, int window_w, int window_h){
		int level = 0;
		int index = 1;
		int num_level_nodes = 1, this_level_nodes = 0;
		int x_leaf_step = 45, y_step = 60, x_step = 0;
		int x_offset = window_w/2;
		int y_offset = 50;
		int numMaxLeafNodes = (int)Math.ceil(Math.pow(2, getNumLevels() - 1));
		node_coordinates = new Point[numData+1];
		while( index <= numData )
		{
			if( checkHeapProperty(index) )
				g.setColor(Color.ORANGE);
			else
				g.setColor(Color.gray);
			
			drawNumberCircle(g, dataArray[index], x_offset, y_offset, node_diameter);
			node_coordinates[index] = new Point(x_offset, y_offset);
			if( index != 1 )
			{
				int parent = index/2;
				drawLine(g, node_coordinates[parent].x, node_coordinates[parent].y, 
						 x_offset, y_offset, node_diameter);
			}
			x_offset += x_step;
			index++;
			this_level_nodes++;
			if( this_level_nodes == num_level_nodes )
			{
				num_level_nodes = 2*num_level_nodes;
				this_level_nodes = 0;
				level++;
				y_offset += y_step;
				x_step = numMaxLeafNodes * x_leaf_step / num_level_nodes;  
				x_offset = (window_w - x_step*(num_level_nodes-1))/2;
			}
		}
	}
	
	static Random rand = new Random(12345);
	
	public BinaryHeap(){
		dataArray = new int[maxSize];
		numData = rand.nextInt(maxSize);
		for( int i=0; i < maxSize; i++ )
			dataArray[i] = 99999999;
		for( int i=1; i <= numData; i++ )
			dataArray[i] = rand.nextInt(100);
	}
	
	// Draws a circle at coordinates (node_x, node_y) with the node_value inside 
	void drawNumberCircle(Graphics g, int node_value, int node_x, int node_y, int diameter)
	{
		g.fillOval( node_x, node_y, diameter, diameter );
		g.setColor(Color.RED);
		g.setFont(new Font("Verdana",Font.BOLD,15));
		g.drawString( ""+node_value, node_x + diameter/2 - 12, node_y + diameter/2 +5 );
	}

	// Draws a line between node1 coordinates (node1_x, node1_y) 
	// and node2 coordinates (node2_x, node2_y)
	void drawLine( Graphics g, int node1_x, int node1_y, int node2_x, int node2_y, int diameter )
	{
		int radius = diameter / 2;
		int x1 = node1_x + radius;
		int y1 = node1_y + radius;
		int x2 = node2_x + radius;
		int y2 = node2_y + radius;
		double dist = Math.sqrt(Math.pow((x1 - x2), 2)+Math.pow((y1 - y2), 2));
		double alpha1 = radius / dist;
		double alpha2 = (dist - radius) / dist;
		int xn1 = (int)(alpha1 * x1 + (1 - alpha1) * x2);
		int yn1 = (int)(alpha1 * y1 + (1 - alpha1) * y2);
		int xn2 = (int)(alpha2 * x1 + (1 - alpha2) * x2);
		int yn2 = (int)(alpha2 * y1 + (1 - alpha2) * y2);

		g.drawLine(xn1, yn1, xn2, yn2);
	}
	
	
}