public class Heap<T extends Comparable<T>> {
private int capacity;
private T[] heap;
private int size;
public Heap(int capacity) {
this.capacity = capacity;
heap = (T[]) new Comparable[capacity];
}
public boolean isEmpty() {
return size == 0;
}
public void insert(T t) {
resize();
heap[size++] = t;
reheapUp(size - 1);
}
public T peek() {
if (isEmpty()) {
return null;
}
return heap[0];
}
public T deleteMin() {
if (isEmpty()) {
return null;
}
T ret = peek();
heap[0] = heap[size - 1];
heap[size - 1] = null;
size--;
reheapDown(0);
resize();
return ret;
}
public T delete(T t) {
if (isEmpty()) {
return null;
}
for (int i = 0; i < heap.length; i++) {
if (heap[i].equals(t)) {
heap[i] = heap[size - 1];
heap[size - 1] = null;
size--;
reheapDown(i);
resize();
return t;
}
}
return null;
}
public void printHeap() {
for (int i = 0; i < heap.length; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
private void reheapUp(int i) {
T tmp = heap[i];
while (i > 0 && tmp.compareTo(heap[getParentIndex(i)]) < 0)
{
swap(i, getParentIndex(i));
i = getParentIndex(i);
}
}
private void reheapDown(int i) {
while (hasLeftChild(i)) {
int leftChildIndex = getLeftIndex(i);
int smallerChildIndex = leftChildIndex;
if (hasRightChild(i)) {
if (heap[getRightIndex(i)].compareTo(heap[leftChildIndex]) < 0) {
smallerChildIndex = getRightIndex(i);
}
}
if (heap[i].compareTo(heap[smallerChildIndex]) > 0) {
swap(i, smallerChildIndex);
} else {
break;
}
i = smallerChildIndex;
}
}
private int getParentIndex(int n) {
return (n - 1) / 2;
}
private int getLeftIndex(int n) {
return 2 * n + 1;
}
private int getRightIndex(int n) {
return 2 * n + 2;
}
private void swap(int i, int j) {
T temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private boolean hasLeftChild(int index) {
return (2 * index + 1) <= (size - 1);
}
private boolean hasRightChild(int index) {
return (2 * index + 2) <= (size - 1);
}
private void resize() {
if (size == capacity) {
heap = Arrays.copyOf(heap, capacity * 2);
} else if (size == capacity / 4) {
heap = Arrays.copyOf(heap, capacity / 2);
}
capacity = heap.length;
}
}