import java.util.Comparator; public class Heap implements MyPriorityQueue { public static final int CAPACITY = 2; private int size; private E[] data; private Comparator comp; @SuppressWarnings("unchecked") public Heap(Comparator comparator) { size = 0; data = (E[]) new Object[CAPACITY]; comp = comparator; } @Override public void offer(E key) { if (size == data.length - 1) { data = doubleSize(data); } size++; int currentIndex = size; data[currentIndex] = key; while (currentIndex != 1 && comp.compare(data[currentIndex], data[currentIndex / 2]) > 0) { swap(currentIndex, currentIndex / 2); currentIndex /= 2; } } @Override public E poll() { if (size == 0) { throw new RuntimeException("No element in the heap"); } E root = data[1]; if (size != 1) { int currentIndex = 1; data[currentIndex] = data[size]; while (currentIndex * 2 < size) { E childToSwap = data[currentIndex * 2]; int nextIndex = currentIndex * 2; if (currentIndex * 2 + 1 < size && comp.compare(data[currentIndex * 2 + 1], data[currentIndex * 2]) > 0) { childToSwap = data[currentIndex * 2 + 1]; nextIndex = currentIndex * 2 + 1; } if (comp.compare(data[currentIndex], childToSwap) >= 0) { break; } swap(currentIndex, nextIndex); currentIndex = nextIndex; } } size--; return root; } @Override public boolean isEmpty() { return size == 0; } private E[] doubleSize(E[] array) { @SuppressWarnings("unchecked") E[] doubleSizeArray = (E[]) new Object[array.length * 2]; for (int i = 0; i < array.length; i++) { doubleSizeArray[i] = array[i]; } return doubleSizeArray; } private void swap(int firstIndex, int secondIndex) { E tmp = data[firstIndex]; data[firstIndex] = data[secondIndex]; data[secondIndex] = tmp; } }