heap.md

###MinHeap

public class minheap<Item extends Comparable<Item>> {
	private int size = 0;
	private int capacity;
	private Item[] array;

	@SuppressWarnings("unchecked")
	minheap() {
		this.capacity = 10;
		array = (Item[]) new Comparable[capacity + 1];
	}

	@SuppressWarnings("unchecked")
	minheap(int x) {
		this.capacity = x;
		array = (Item[]) new Comparable[x + 1];
	}

	public void createHeap(Item[] input) {
		if (input.length > 0) {
			for (int i = 0; i < input.length; i++) {
				add(input[i]);
			}
		}
	}

	public void display(){
		for(int i = 1; i < array.length; i++){
			System.out.print(" " + array[i]);
		}
		System.out.println("");
	}

	public void add(Item item) {
		if (size == capacity + 1) {
			if (array[size].compareTo(item) > 0) {
				array[size] = item;
				siftup();
			}
		} else {
			array[++size] = item;
			siftup();
		}
	}

	public void siftup() {
		int i = size;
		while (i > 1 && array[i].compareTo(array[i / 2]) < 0) {
			swap(array, i, i / 2);
			i = i / 2;
		}
	}

	public void swap(Item[] array, int index1, int index2) {
		Item temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}

	public void siftdown(int index) {
		int smallest = index;

		while (index <= capacity) {
			if (index * 2  <= size && array[index * 2].compareTo(array[smallest]) < 0) {
				smallest = index * 2;
			}
			if (index * 2 + 1 <= size && array[index * 2 + 1].compareTo(array[smallest]) < 0) {
				smallest = index * 2 + 1;
			}

			if (smallest == index) {
				break;
			}
			swap(array, smallest, index);
			index = smallest;
		}
	}

	public Item extractMin() {
		Item min = getMin();
		swap(array, 1, size);
		array[size--] = null;
		siftdown(1);
		return min;
	}

	public Item getMin() {
		return array[1];
	}

	public void delete(Item item) {
		int i = 1;
		for (i = 1; i <= size; i++) {
			if (array[i] == item) {
				swap(array, i, size);
				array[size--] = null;
				siftdown(i);
				break;
			}
		}
	}

	public int size() {
		return size;
	}

	@SuppressWarnings("unchecked")
	public static void main(String args[]){

		Integer arrA [] = {3,2,1,7,8,4,10,16,12};
		System.out.println("Original Array : ");
		for(int i = 0; i<arrA.length; i++){
			System.out.print("  " + arrA[i]);
		}
		System.out.println();

		@SuppressWarnings("rawtypes")
		minheap heap = new minheap(arrA.length);
		System.out.print("\n Min-Heap : ");
		heap.createHeap(arrA);
		heap.display();

		System.out.print("Extract Min :");
		for(int i=0; i < arrA.length; i++){
			System.out.print("  " + heap.extractMin());
			System.out.print("\n Min-Heap : ");
			heap.display();
		}

	}
}