heapsort.java

package nLogN;

import java.util.Arrays;

public class Seven53_heapsort {

	static int array[] = { 6, 2, 22, 77, 12, 8, 22, 123, 12, 12 };
	static int left;
	static int right;
	static int highest;
	static int length;
	static int temp;

	static void initHeapify(int[] array) {
		length = array.length - 1;
		for (int i = (length / 2); i >= 0; i--) {
			maxValue(i);
		}
		
		for (int i = length; i > 0; i--) {
			exchange(i , 0);
			length--;
			maxValue(0);
		}
	}

	static void exchange(int low, int high) {
		temp = array[high];
		array[high] = array[low];
		array[low] = temp;
	}

	static void maxValue(int parent) {
		left = (parent * 2);
		right = (parent * 2) + 1;
		if (left <= length && array[left] > array[parent]) {
			exchange(parent, left);
			highest = left;
		} else {
			highest = parent;
		}
		if (right <= length && array[right] > array[parent]) {
			exchange(parent, right);
			highest = right;
		} else {
			highest = parent;
		}
		if (highest != parent) {
			maxValue(highest);
		}
	}

	static void sort(int[] array) {
		length = array.length;
		initHeapify(array);
	}

	public static void main(String[] args) {

		System.out.println("initial array: " + Arrays.toString(array));
		initHeapify(array);
		System.out.println("initial array: " + Arrays.toString(array));
	}

}