package DataStructures;

import java.util.NoSuchElementException;

/**
 * Binary heap implementation of a priority queue.<p>
 *
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/lang/Comparable.html">Comparable</a>
 * @see DataStructures.StrictBinaryHeap
 * @param <E> the type of elements held in this heap
 * @author Peter Williams
 */

public class BinaryHeap<E extends Comparable<? super E>> 
    implements PriorityQueue<E> {

    private E[] heap;  // the heap
    private int size;  // number of items in the heap
  
    /**
     * Constructs an empty binary heap suitable for holding elements of type E.
     */
    public BinaryHeap() {
        heap = (E[])new Comparable[1];
        size = 0;
    }
  
    /**
     * Tests if the heap is empty.
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns the current size of the queue
     */
    public int size() {
        return size;
    }
  
    /**
     * Adds an item to the heap.
     */
    public void add(E item) {
        // grow the heap if necessary
        if (size == heap.length) {
            E[] newHeap = (E[])new Comparable[2 * heap.length];
            System.arraycopy(heap, 0, newHeap, 0, heap.length);
            heap = newHeap;
        }
        // find where to insert while rearranging the heap if necessary
        int parent, child = size++; // the next available slot in the heap
        while (child > 0 && heap[parent = (child - 1) / 2].compareTo(item) < 0) {
            heap[child] = heap[parent];
            child = parent;
        }
	heap[child] = item;
    }
  
    /**
     * Removes an item of highest priority from the heap.
     */
    public E remove() {
	if (size == 0) {
	    throw new NoSuchElementException();
	}
	E result = heap[0];   // to be returned
	E item = heap[--size]; // to be reinserted 
	int child, parent = 0; 
	while ((child = (2 * parent) + 1) < size) {
	    // if there are two children, compare them
	    if (child + 1 < size && heap[child].compareTo(heap[child + 1]) < 0) {
		++child;
	    }
	    // compare item with the larger
	    if (item.compareTo(heap[child]) < 0) {
		heap[parent] = heap[child];
		parent = child;
	    } else {
		break;
	    }
	}
	heap[parent] = item;
	return result;
    }

}