import java.util.Arrays;public class Solution {    /**     * 每次将堆顶元素交换到最后并从堆中除掉。     *      * @param a     */    public static void heapSort(int[] a) {        buildHeap(a);        int n = a.length - 1;        for (int i = a.length - 1; i > 0; i--) {            swap(a, 0, i);            // 堆的大小每次减1            maxHeapify(a, n--, 0);        }    }    /**     * O(n)时间建堆     */    private static void buildHeap(int[] a) {        for (int i = a.length / 2; i >= 0; i--)            maxHeapify(a, a.length, i);    }    /**     * n 表示当前堆的大小     */    private static void maxHeapify(int[] a, int n, int i) {        int l = left(i);        int r = right(i);        int largest = i;        if (l < n && a[l] > a[i])            largest = l;        if (r < n && a[r] > a[largest])            largest = r;        if (largest != i) {            swap(a, i, largest);            maxHeapify(a, n, largest);        }    }    private static void swap(int[] a, int i, int j) {        int tmp = a[i];        a[i] = a[j];        a[j] = tmp;    }    private static int left(int i) {        return 2 * i + 1;    }    private static int right(int i) {        return 2 * i + 2;    }    public static void main(String[] args) {        int[] a = { 2, 8, 7, 1, 3, 5, 6, 4 };        System.out.println("before sorting:" + Arrays.toString(a));        heapSort(a);        System.out.println("after sortint:" + Arrays.toString(a));    }}