Heap

Heap.java

import java.util.Arrays;

/**
 * Implements a size limited heap
 * 
 * @author Daniel Kohlsdorf
 */
public class Heap {

	private double heap[];
	private int heapSize;

	public Heap(int size) {
		heap = new double[size];
		heapSize = 0;
	}

	// insert onto end and swap up
	public void insert(double value) {
		heapSize++;
		heap[heapSize - 1] = value;
		up(heapSize - 1);
	}

	// remove front, get last element
	// and swap downwards
	public void remove() {
		heapSize--;
		heap[0] = heap[heapSize];
		heap[heapSize] = 0;
		down(0);
	}

	// swap value upwards
	public void up(int idx) {
		if (idx > 0) {
			int parent = (idx - 1) / 2;
			while (heap[idx] < heap[parent]) {
				double tmp = heap[parent];
				heap[parent] = heap[idx];
				heap[idx] = tmp;
				idx = parent;
				parent = (idx - 1) / 2;
			}
		}
	}

	// swap value downwards
	public void down(int idx) {
			int leftChild = 2 * idx + 1;
			int rightChild = 2 * idx + 2;
			int minIndex = rightChild;
			if(rightChild >= heapSize && leftChild >= heapSize) {
				return;
			} else if(rightChild >= heapSize) {
				minIndex = leftChild;
			} else if (heap[leftChild] < heap[rightChild]) {
				minIndex = leftChild;
			} 
			if (heap[idx] > heap[minIndex]) {
				double tmp = heap[idx];
				heap[idx] = heap[minIndex];
				heap[minIndex] = tmp;
				down(minIndex);
			} 
	}

	@Override
	public String toString() {
		return Arrays.toString(heap);
	}

	public static void main(String[] args) {
		Heap heap = new Heap(10);
		System.out.println(heap);
		heap.insert(1);
		System.out.println(heap);
		heap.insert(2);
		System.out.println(heap);
		heap.insert(20);
		System.out.println(heap);
		heap.insert(12);
		System.out.println(heap);
		heap.insert(14);
		System.out.println(heap);

		heap.remove();
		System.out.println(heap);
		heap.remove();
		System.out.println(heap);
		heap.remove();
		System.out.println(heap);

	}
}