GitHub Viewer
/**
* http://algs4.cs.princeton.edu/24pq/
* min heap: only keep the min at the top, parent(root) < left and right node
*/
public class MinHeap {
private int maxSize;
private int current;
private int[] heap;
public MinHeap(int max) {
maxSize = max;
heap = new int[maxSize + 1]; // min is heap[1], it easy to calculate left/right
current = 0; // current index
}
public void insert(int value) {
if (current == maxSize) {
throw new RuntimeException("Heap is full!");
}
heap[++current] = value; // start from 1
shiftUp(current);
}
public boolean isEmpty() {
return current == 0;
}
public int min() {
if (isEmpty())
throw new RuntimeException("heap is empty");
return heap[1];
}
public int removeMin() {
if (isEmpty())
throw new RuntimeException("heap is empty");
int min = heap[1];
swap(1, current);
// heap[current] = Integer.MAX_VALUE;
current--;
if(current != 0 )
shiftDown(1);
return min;
}
private void shiftUp(int k) {
// k/2 is parent, parent < left/right
while (k > 1 && heap[k / 2] > heap[k]) {
swap(k / 2, k);
k = k / 2;
}
}
private void shiftDown(int k) {
while (2 * k heap[j]) {
i++; // i = j
}
if (heap[k] < heap[i]) {
break;
}
swap(k, i);
k = i;
}
}
private void swap(int i, int j) {
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
// is pq[1..N] a min heap?
private boolean isMinHeap() {
return isMinHeap(1);
}
// is subtree of pq[1..N] rooted at k a min heap?
private boolean isMinHeap(int k) {
if (k > current) return true;
int left = 2 * k, right = 2 * k + 1;
if (left heap[left]) return false;
if (right heap[right]) return false;
return isMinHeap(left) && isMinHeap(right);
}
public void printHeap() {
System.out.print("heap: ");
for (int i = 1; i