// Adam Campbell
// 3/10/05
// Solution to COP 3530 Homework #3 Programming Problem

public class Heap{

	private int numElements;
	private Comparable[] list;
	
	// simple Heap constructor
	public Heap(int size){
	
		numElements = 0;
		list = new Comparable[size];
		
	}
	
	// returns true if there are no elements in this Heap
	public boolean isEmpty(){
	
		return numElements == 0;
	
	}
	
	// adds an element to the set
	public void add(Comparable obj){
		
		// put it at the end of the list
		list[numElements] = obj;
		
		// and then sift it up
		siftUp(numElements);
		
		numElements++;
		
	}
	
	// removes the element from the top of the list
	// replaces the top of the list with the bottom element, 
	//   and then sifts this element down
	public Comparable removeTop(){
	
		if(isEmpty()) return null;
		
		Comparable toReturn = list[0];
		
		list[0] = list[--numElements];
		
		siftDown(0);
		
		return toReturn;
	}
	
	// sifts the element at index up
	private void siftUp(int index){
	
		if(index == 0) return;
		
		if(list[index].compareTo(list[getParentIndex(index)]) < 0){
		
			swap(index, getParentIndex(index));
			siftUp(getParentIndex(index));
						
		}
		
	}
	
	// sifts the element at index down
	private void siftDown(int index){
	
		int leftChildIndex = getLeftChildIndex(index);
		int rightChildIndex = getRightChildIndex(index);
		
		// there are no children
		if(leftChildIndex >= numElements) return;
		
		// if there is no right child, or the left child is less than the right child, sift to the left
		if(rightChildIndex == numElements || list[leftChildIndex].compareTo(list[rightChildIndex]) < 0){
		
			// sifts down if the element is bigger than its child
			if(list[leftChildIndex].compareTo(list[index]) < 0){
			
				swap(index, leftChildIndex);
				siftDown(leftChildIndex);
				
			}
		
		// otherwise, sift to the right
		}else{
		
			// sifts down if the element is less than its child
			if(list[rightChildIndex].compareTo(list[index]) < 0){
			
				swap(index, rightChildIndex);
				siftDown(rightChildIndex);
				
			}
					
		}
		
	}
	
	private void swap(int index1, int index2){
	
		Comparable tmp = list[index1];
		list[index1] = list[index2];
		list[index2] = tmp;
		
	}
	
	private int getParentIndex(int index){
	
		return (index-1)/2;
		
	}
	
	private int getLeftChildIndex(int index){
	
		return index*2 + 1;
		
	}
	
	private int getRightChildIndex(int index){
	
		return index*2 + 2;
		
	}
		
}