public class alg2kekolajittelu {

	private static Random rand = new Random();

	public static void main(String[] args) {

		int n = rand.nextInt(20) + 5;
		int[]a = new int[n];
		a[0] = n - 1;
		muodostaTaulukko(a, n);
		kekolajittelu(a, a[0]);
		a[0] = n - 1;

		for(int i=0;i<a.length;i++){
            System.out.print(a[i] + " ");
               }
	}

	private static void kekolajittelu(int[] a, int n) {
		teeKeko(a);
		for (int i = n; i > 1; i--) {
			int apu = a[1];
			a[1] = a[i];
			a[i] = apu;
			a[0]--;
			korjaaKeko(a,1);
              }
	}

	public static void muodostaTaulukko(int[]a, int n) {
		for (int i = 1; i < n - 1; i++) {
		int arvottuLuku = rand.nextInt(1000);
		a[i] = arvottuLuku;
		}
	}

	public static void teeKeko(int[]a) {
		for (int i = a[0]/2; i>=1;i--){
			korjaaKeko(a,i);
		}
	}

	private static void korjaaKeko(int[] a, int i) {
		if (2*i > a[0])
			return;
		int j = 2*i;
		int alkio = a[i];
		while (j <= a[0]) {
			if ((j < a[0]) && (a[j] > a[j+1]))
				j = j+1;
			if (alkio <= a[j])
				break;
			a[j/2] = a[j];
			j=2*j;
		}
		a[j/2] = alkio;
		}
	}