HeapSort

import java.util.Arrays;

public class HeapSort  {
	public static void main(String[] args) {
		int[] arr = new int[]{12, 4, 76, 14, 100, 1, 3};
		/*for (int i = 0; i != arr.length; i++) {
			heapInsert(arr, arr[i], i);
		}*/
		for (int i = (arr.length-1)/2; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
		for (int i = arr.length-1; i > 0 ; i--) {
			int tmp = arr[i];
			arr[i] = arr[0];
			arr[0] = tmp;
			heapify(arr, 0, i);
		}
		System.out.println(Arrays.toString(arr));
	}
	public static void heapInsert(int[] arr, int value, int index) {
		arr[index] = value;
		while (index != 0) {
			int parent = (index-1)/2;
			if (arr[parent] < arr[index]) {
				int tmp = arr[parent];
				arr[parent] = arr[index];
				arr[index] = tmp;
			} else {
				break;
			}
			index = parent;
		}
	}
	public static void heapify(int[] arr, int index, int heapSize) {
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		int largest = index;
		while (left < heapSize) {
			if (arr[left] > arr[index]) {
				largest = left;
			}
			if (right < heapSize && arr[right] > arr[largest]) {
				largest = right;
			}
			if (largest != index) {
				int tmp = arr[largest];
				arr[largest] = arr[index];
				arr[index] = tmp;
			} else {
				break;
			}
			index = largest;
			left = index * 2 + 1;
			right = index * 2 + 2;
		}
	}
}