package dataStructures;

import java.util.ArrayList;

public class BinaryMinHeap<T extends Comparable<T>> implements PriorityQueue<T> {

	private ArrayList<T> arr;
	private int size;
	private final int DEFAULT_SIZE = 101;
//	private final double LOAD_FACTOR = 0.75;
	
	public BinaryMinHeap() {
		arr = new ArrayList<T>(DEFAULT_SIZE);
		arr.add(0, (T) null);
		size = 0;
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}

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

	@Override
	public T findMin() {
		if(isEmpty())
			throw new EmptyHeapException("Queue must have at least one entry");
		return arr.get(1);
	}

	@Override
	public void insert(T x) {
		
		// increment size of heap
		++size;
		
		// insert value to the end of the data structure
		arr.add(size, x);
		
		// percolate up
		int hole = size;
		while(hole > 1 && ((arr.get(hole/2).compareTo(arr.get(hole))) > 0)) {
			T child = arr.get(hole/2);
			arr.add(hole/2, arr.get(hole));
			arr.add(hole, child);
			hole /= 2;
		}
	}

	@Override
	public T deleteMin() {
		
		if(isEmpty())
			throw new EmptyHeapException("Queue must have at least one entry");
		
		T retVal = arr.get(1);
		
		// copying last element to the top
		arr.add(1, arr.get(size));
		
		// percolate down
		int curIndex = 1;
		while(curIndex <= size/2) {
			int childIndex = 2*curIndex;
			if(arr.get(childIndex).compareTo(arr.get(childIndex+1)) > 0 && childIndex+1 <= size) 
				childIndex++;
			if(arr.get(childIndex).compareTo(arr.get(curIndex)) > 0)
				break;
			T childVal = arr.get(childIndex);
			arr.add(childIndex, arr.get(curIndex));
			arr.add(curIndex, childVal);
			curIndex = childIndex;
		}
		size--;		
		return retVal;
	}

	@Override
	public void makeEmpty() {
		arr = new ArrayList<T>();
		size = 0;
	}
}

@@ -343,20 +343,16 @@
 d(0,
- (T)
  null);%0A
 %09%09si
@@ -347,16 +347,16 @@
  null);%0A
+
 %09%09size =
@@ -701,24 +701,63 @@
 %09++size;%0A%09%09%0A
+%09%09arr.ensureCapacity(DEFAULT_SIZE);%0A%09%09%0A
 %09%09// insert 
@@ -960,27 +960,27 @@
 /2);%0A%09%09%09arr.
-add
+set
 (hole/2, arr
@@ -999,19 +999,19 @@
 %0A%09%09%09arr.
-add
+set
 (hole, c
@@ -1238,19 +1238,19 @@
 p%0A%09%09arr.
-add
+set
 (1, arr.
@@ -1364,32 +1364,56 @@
 curIndex;%0A%09%09%09if(
+childIndex+1 %3C= size && 
 arr.get(childInd
@@ -1456,32 +1456,8 @@
  %3E 0
- && childIndex+1 %3C= size
 ) %0A%09
@@ -1588,19 +1588,19 @@
 %0A%09%09%09arr.
-add
+set
 (childIn
@@ -1631,19 +1631,19 @@
 %0A%09%09%09arr.
-add
+set
 (curInde

converted to generic