// 堆排序
    public static void heapSort(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            maxHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i >= 1; i--) {
            arr[0] ^= arr[i];
            arr[i] ^= arr[0];
            arr[0] ^= arr[i];
            maxHeap(arr, 0, i);
        }
    }

    // 建最大堆
    private static void maxHeap(int[] arr, int index, int end) {
        int q;
        while (index < end) {
            q = 2 * index + 1;
            if (q >= end)
                break;
            if ((q < end - 1 && (arr[q + 1] > arr[q])))
                q = q + 1;
            // 如果某一节点的值小于其子节点的最大值，将其交换
            if (arr[q] > arr[index]) {
                arr[q] ^= arr[index];
                arr[index] ^= arr[q];
                arr[q] ^= arr[index];
                index = q;
            } else {
                break;
            }
        }
    }