// adapted from Carrano&Savitch; modified a bit from MaxheapAsArray
// Data Structures & Abstractions with Java, Prentice Hall, 2003

public class Heap implements SeqStructure {

    private Object[] heap;
    private int MAXSIZE;
    private int size; // also gives pointer to last index in heap

    // default size -- need at least 0th array location
    //                 need at least 1 free location for put
    public Heap( ) { this(2); } 

    public Heap(int size) {
	if (size >=0 && size < 2)
	    size = 2;
	if (size < 0) {
	    System.err.println("Must make initial heap size at least 2!");
	    System.exit(0);
	}
	    
	MAXSIZE = size;
	heap = new Object[MAXSIZE];
    }	

    public Heap(Object[] stuff) {
	MAXSIZE = size = stuff.length+1;                   // set # of elems and allotted space
	heap = new Object[MAXSIZE];                        // need to have empty 0th pos
	System.arraycopy(stuff,0,heap,1,MAXSIZE);          // copy stuff into unheaped heap
	for (int i = heap.length/2; i > 0; i--) reheap(i); // start at root and work "down"
    }

    public void put(Object o) {
	size++; // increment size more this new item
	if (size >= MAXSIZE) increaseHeapSize(); // increase array if out of space

	int index = size;      // index of current free location
	int parent = index/2;  // parent of free location

	// Until reaching root, move the parents down while the item o > parents:
	while (index > 1 && ((Comparable) o).compareTo(heap[parent]) > 0) {
	    heap[index]=heap[parent]; // move parent down to child pos
	    index = parent;           // update index
	    parent = index/2;         // update parent
	}
	
	// done finding appropriate location to maintain heapness:
	heap[index] = o;
    }

    private void increaseHeapSize() { // increase 1 -- probably should double :-)
	int oldsize = MAXSIZE;
	MAXSIZE++;
	Object[] tmp = new Object[MAXSIZE];
	System.arraycopy(heap,0,tmp,0,oldsize); // source, sourse pos, dest, dest pos, length
	heap = tmp;
    }

    public Object get() {
	Object root = null;
	if (!isEmpty()) {
	    root = heap[1];     // max item to return
	    heap[1]=heap[size]; // move most recent item to root
	    size--;             // reduce size
	    reheap(1);          // reheap entire tree
	}
	return root;
    }
    
    private void reheap(int rootIndex) {
	Object orphan = heap[rootIndex];       // root that might need to be moved to reheap
	int largerChild = 2*rootIndex;         // current index of leftChild
	boolean done = false;                  // need to keep going	

	while (!done && (largerChild <= size)) {
	    int rightChild = largerChild + 1;
	    if ((rightChild <= size) && 
		((Comparable) heap[rightChild]).compareTo(heap[largerChild]) > 0)
		largerChild = rightChild;
	    if ( ((Comparable) orphan).compareTo(heap[largerChild]) < 0) {
		heap[rootIndex]=heap[largerChild];
		rootIndex = largerChild;
		largerChild = 2*rootIndex;
	    }
	    else
		done = true;
	}
	heap[rootIndex] = orphan;
    }

    public boolean isEmpty() {	return size == 0; }
    
    public int size() {	return this.size; }
    
    public String toString() {
	String s = "HeapAsArray: [";
	for (int i=1; i<=size; i++) {
	    s+=heap[i];
	    if (i < size) s+=",";
	}
	s += "]";
	return s;
    }

}