import java.util.Arrays;

public class HeapSortCompleto {

	public void heapSort(int[] valores) {
		buildMaxHeap(valores);
		int comprimento = valores.length;

		for (int i = valores.length - 1; i > 0; i--) {
			swap(valores, i, 0);
			maxHeapify(valores, 0, --comprimento);
		}
	}

	private void buildMaxHeap(int[] v) {
		for (int i = v.length / 2 - 1; i >= 0; i--)
			maxHeapify(v, i, v.length);
	}

	private void maxHeapify(int[] v, int pos, int n) {
		int maxi;
		int l = 2 * pos + 1;
		int right = 2 * pos + 2;
		if ((l < n) && (v[l] > v[pos])) {
			maxi = l;
		} else {
			maxi = pos;
		}
		if (right < n && v[right] > v[maxi]) {
			maxi = right;
		}
		if (maxi != pos) {
			swap(v, pos, maxi);
			maxHeapify(v, maxi, n);
		}
	}

	private void swap(int[] v, int j, int aposJ) {
		int aux = v[j];
		v[j] = v[aposJ];
		v[aposJ] = aux;
	}
	
	public static void main(String... args) {
		int[] valores = { 4, 6, 8, 1, 5, 2 };

		HeapSortCompleto hs = new HeapSortCompleto();
		hs.heapSort(valores);

		System.out.println(Arrays.toString(valores));
	}



}
