/********************************************************************************
 * File name: BinaryHeap.java
 * Description: The class of binary heap which implements PriorityQ interface.
 *              public operation see the PriorityQ.java.
 * Last change: Feb 9th, 2003
 ********************************************************************************/



public class BinaryHeap implements PriorityQ
{

	public int currentSize;
	
	public String[] heap;
	
/*********************************************************************************/
	
	public BinaryHeap()
	{ //construct a new array have capacity of 100 and the currently heap size is 0
		heap = new String[100];
		currentSize = 0;
	}
	
/**********************************************************************************
 *		
 *	public BinaryHeap( String[] array )
 *	{ //constructor of an existed array which the heap size is equal to the length
 *		currentSize = array.length;
 *		heap = new String[ elements.length + 1 ];
 *	}
 *	
 **********************************************************************************/
	
	public void insert( String element )
	{  
	    //post: insert a new element into the queue and the size increment.
	    //      call the swap() function to finish the insertion.  
		int hole = ++currentSize;
		heap[0] = element;
		
		heap[ percolateUp(hole) ] = element;
	}
	
/**********************************************************************************/ 
	
	private int percolateUp( int hole )
	{ 
	  //pre: input the last number of the array
	  //post: output the right position for placing the new element.
		if ( heap[0].compareTo( heap[hole/2] ) >= 0 )
			return hole;
		
		else
		{
			heap[hole] = heap[hole/2];
			return percolateUp( hole/2 );
		}
	}
	
/**********************************************************************************/
	
	public String deleteMin()   
	{ 
	  //pre: the queue is not empty
	  //post: the smallest item in the queue will be removed,
	  //      and call the reBuild() function to restore the elements.
		String minElement = findMin();
		heap[0] = heap[currentSize];
		
		currentSize--;
		
		heap[ percolateDown(1) ] = heap[0];
		
		return minElement;
	}	
	
/**********************************************************************************/
	
	private int percolateDown( int hole )
	{ 
	  //pre: input the hole which the element has been removed
	  //post: output the hole to store the last element in the array,
	  //      and restore the queue into binary heap.				
		if ( hole *2 > currentSize )
			return hole;
			
		if ( heap[0].compareTo( heap[hole*2] ) < 0 && heap[0].compareTo( heap[hole*2+1] ) < 0 )
			return hole;
			
		else if ( heap[hole*2].compareTo( heap[hole*2+1] ) < 0 )
		{
			heap[hole] = heap[hole*2];
			return percolateDown( hole*2 );
		}
		
		else
		{
			heap[hole] = heap[hole*2+1]; 
			return percolateDown( hole*2+1 );	
		}		
	}
			
/**********************************************************************************/	
		
	public String findMin()  
	{ //post: return the smallest item in the queue;
	  //      produce an error message when the queue is empty
		if( isEmpty() )
		{
			System.out.println( "Empty heap, invalid operation. " );
			return "nothing";
		}
		return heap[1];
	}
	
/**********************************************************************************/
	
	public boolean isEmpty()  
	{ //post: return true if empty; false otherwise
		if ( currentSize < 0 )
			currentSize = 0;
		return currentSize == 0;
	}
	
/**********************************************************************************/
	
	public int size()  
	{ //post: returns current size
		if ( currentSize < 0 )
			currentSize = 0;
		return currentSize;
	}
	
/**********************************************************************************/
	
	public void makeEmpty()  
	{ //post: remove all items
		heap = new String[100];
		currentSize = 0;
	}
	
/**********************************************************************************/

	public void printHeap()
	{ //post: prints the whole queue
		/*for ( int i = 1; i <= currentSize; i = i*2 )
		 *{
		 	for ( int j = i; j < i*2; j++ )
		 		System.out.print( "--" + heap[j] + "--" );
		 	System.out.println();
		 }*/
		
		for ( int i = 1; i <= currentSize; i++ )
			System.out.print( "-- " + i + "--" );
			
		System.out.println();
		
		for ( int i = 1; i <= currentSize; i++ )
			System.out.print( "--" + heap[i] + "--" );						
		
		
		
	}
	
/**********************************************************************************/
	
} //class ends