HeapSort.java

public class HeapSort {
	
	public static void sort(int[] a)
	{
		int heapSize = a.length-1;
		buildMaxHeap(a, heapSize);
		
		while (heapSize > 0) {
			swap(a, 0, heapSize);
			heapSize--;
			heapify(a, 0, heapSize);
		}
	}
	
	private static void buildMaxHeap(int[] a, int heapSize)
	{
		int nonLeaf = (heapSize-1)/2;
		
		for (int i = nonLeaf; i >= 0; i--) {
			heapify(a, i, heapSize);
		}
	}
	
	private static void heapify(int[] a, int i, int heapSize)
	{
		int left = (2*i) + 1;
		int right = (2*i) + 2;
		int largest;
		
		if (left <= heapSize && a[left] > a[i]) {
			largest = left;
		} else {
			largest = i;
		}
		
		if (right <= heapSize && a[right] > a[largest]) {
			largest = right;
		}
		
		if (largest != i) {
			swap(a, i, largest);
			heapify(a, largest, heapSize);
		}
	}
	
	private static void swap(int[] a, int i, int j)
	{
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

}