/**
 * @author gtowell
 * Created April 6, 2020
 * Modified: April 12, 2021
 * Modified: April 4, 2022
 */
@SuppressWarnings("unchecked")
public class BinaryHeap<K extends Comparable<K>, V> extends AbstractPriorityQueue<K, V>
{

	protected static final int CAPACITY = 1032;
	protected Pair<K,V>[] backArray;
    protected int size;

	public BinaryHeap() {
        this(CAPACITY);
	}
	
	public BinaryHeap(int capacity) {
        backArray = new Pair[capacity];
	}

    @Override
    public int size()
    {
		return size;
    }

    @Override
    public boolean isEmpty()
    {
		return size==0;
    }

    @Override
    public boolean offer(K key, V value)
	{
		if (size >= (backArray.length - 1))
			return false;
		int loc = size++;
		backArray[loc] = new Pair<K, V>(key, value);
		int upp = (loc - 1) / 2;
		while (loc != 0) {
			if (0 > backArray[loc].compareTo(backArray[upp])) {
				Pair<K, V> tmp = backArray[upp];
				backArray[upp] = backArray[loc];
				backArray[loc] = tmp;
				loc = upp;
				upp = (loc - 1) / 2;
			} else {
				break;
			}
		}
		return true;
	}
	
	protected void removeTop()
    {
		size--;
		backArray[0] = backArray[size];
		backArray[size]=null;
		int parentLoc=0; 
		while (true) 
		{
	    	int bestChildLoc;   
	    	int childLoc1 = parentLoc*2+1; 
	    	int childLoc2 = parentLoc*2+2; 
	    	if (childLoc1>=size) 
				break;           
	    	if (childLoc2>=size)
	    	{
				bestChildLoc=childLoc1; 
	    	}
	    	else
	    	{
				int cmp = backArray[childLoc1].compareTo(backArray[childLoc2]);
				if (cmp<=0)
		    		bestChildLoc=childLoc1;
				else
		    		bestChildLoc=childLoc2;
			}
			
	    	if (0 > backArray[bestChildLoc].compareTo(backArray[parentLoc]))
	    	{
				Pair<K,V> tmp = backArray[bestChildLoc];
				backArray[bestChildLoc] = backArray[parentLoc];
				backArray[parentLoc] = tmp;
				parentLoc=bestChildLoc;
	    	}
	    	else {
				break;
	    	}
		}
    }

	@Override
	public V poll() {
		if (isEmpty())
			return null;
		Pair<K,V> tmp = backArray[0];
		removeTop();
		return tmp.theV;
	}

	@Override
	public V peek() {
		if (isEmpty())
			return null;
		return backArray[0].theV;
	}


	public static void main(String[] args) {
		BinaryHeap<Integer, String> pq = new BinaryHeap<>(CAPACITY);
		pq.offer(1, "Jane");
		pq.offer(10, "WET");
		pq.offer(5, "WAS");
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println();

		pq = new BinaryHeap<>(CAPACITY);
		pq.offer(2, "Jane");
		pq.offer(1, "WET");
		pq.offer(5, "WAS");
		System.out.println(pq.poll());
		System.out.println(pq.poll());
		System.out.println(pq.poll());
	}

}