import java.util.Scanner;

public class HeapSort {
	private static int N;

	public static void sort(int array[]) {
		max_heapify(array);
		for (int i = N; i > 0; i--) {
			swap(array, 0, i);
			N = N - 1;
			maxheap(array, 0);
		}
	}

	public static void max_heapify(int array[]) {
		N = array.length - 1;
		for (int i = N / 2; i > 0; i--) {

			// if ((2*i)>N)
			// i=0;
			maxheap(array, i);
		}
	}

	public static void maxheap(int arr[], int i) {
		int left = 2 * i;
		int right = 2 * i + 1;
		int max = i;
		if (left  arr[i])
			max = left;
		if (right  arr[max])
			max = right;

		if (max != i) {
			swap(arr, i, max);
			
			maxheap(arr, max);
			/*
			 * for (int j=0;j