public class Heap {

	public static void sort(int[] a) {
		int N = a.length;
		// 构建heap
		for (int i = N / 2 - 1; i >= 0; i--) {
			sink(a, i, N - 1);
		}
		// 排序
		while (N > 1) {
			exch(a, 0, N - 1);
			N--;
			sink(a, 0, N - 1);
		}
	}

	private static void sink(int[] pq, int k, int n) {
		while (2 * k + 1 <= n) {
			int j = 2 * k + 1;
			if (j + 1 <= n && less(pq, j, j + 1)) {
				j++;
			}
			if (!less(pq, k, j)) {
				break;
			} else {
				exch(pq, k, j);
				k = j;
			}
		}
	}

	public static void show(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

	private static boolean less(int[] pq, int i, int j) {
		return pq[i] < pq[j];
	}

	private static void exch(int[] pq, int i, int j) {
		int temp = pq[i];
		pq[i] = pq[j];
		pq[j] = temp;
	}
}