public class HeapSort {
    /**
     * 传说中的堆排序，用于大量数据，
     * 本次采用小根堆排序。
     * 其原理，你在网上搜一下堆排序图
     * 解就能一目了然。
     * 现在我想要得到一个递减的有序序
     * 列，就应该使用小根堆来做。
     * 个人感觉堆排序有点麻烦
     * 堆是个完全二叉树，所以可以应用
     * 定理——非叶子结点序号乘以2+1是其
     * 左孩子结点的序号。
     * 反之，数组长度除以2-1就是父结点
     * 的序号。
     * @param sourceArray
     */
    static public void heapSort0(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        //一开始的时候由数组构成的二叉树是完全二叉树，
        // 但是还称不上是小根堆，需要先进行调整才行。
        // 是从最后一个非叶子结点往上开始的。
        for (int counter = arrayLength / 2 - 1;counter > -1;counter--)
            HeapSort.adjustToSmallHeap(sourceArray,counter,arrayLength);
        //打印初始化完毕的根堆
        int twoPower = 1;
        int stepTwoPower = twoPower;
        for (int counter = 0;counter < arrayLength;counter++) {
            System.out.print(sourceArray[counter] + " ");
            if ((counter + 1) % stepTwoPower == 0) {
                twoPower *= 2;
                stepTwoPower += twoPower;
                System.out.println();
            }
        }
        System.out.println("\n根堆初始化完毕\n");
        //如此一来完全二叉树变成了有序的小根堆，
        // 堆顶的结点就是整个数组最小的值。
        // counter>0就可以了，因为此时待
        // 调整的元素只有2个，它俩调整完了就不需要调整了。
        for (int counter = arrayLength - 1;counter > 0;counter--) {
            //把最小值放到数组最后面。
            int tempElement = sourceArray[counter];
            sourceArray[counter] = sourceArray[0];
            sourceArray[0] = tempElement;
            //打印交换发生以后的根堆
            System.out.println("打印倒数第" + counter + "次交换以后的数组");
            int twoPower0 = 1;
            int stepTwoPower0 = twoPower0;
            for (int counter0 = 0;counter0 < arrayLength;counter0++) {
                System.out.print(sourceArray[counter0] + " ");
                if ((counter0 + 1) % stepTwoPower0 == 0) {
                    twoPower0 *= 2;
                    stepTwoPower0 += twoPower0;
                    System.out.println();
                }
            }
            //此时原来的根堆发生了混乱，
            // 但是此时不需要管上一次
            // 根堆的最后一个结点了。
            System.out.println("\n倒数" + counter + "调整开始");
            HeapSort.adjustToSmallHeap(sourceArray,0,counter);
            for (int element:sourceArray)System.out.print(element + " ");
            System.out.println("\n倒数" + counter + "调整完成\n");
        }
    }

    /**
     * 不过本步骤有一个前期，
     * 那就是它会认为本次调整
     * 的结点下面的结点全都是
     * 已经调整好的，不然得出
     * 的结果是错误的。所以很
     * 显然第一次调整的时候的
     * rootIndex必须是最后一
     * 个非叶子结点才行。
     * 本方法是要把一个非小
     * 根堆调整成小根堆的方法
     * 也是堆排序的核心所在
     * @param sourceArray
     * @param rootIndex 需要调整的堆的顶部结点的index
     * @param adjustLength 需要调整的长度
     */
    static public void adjustToSmallHeap(int[] sourceArray,int rootIndex,int adjustLength) {
        //应用定理父结点的序号等于
        // 该结点所在长度除以2再减
        // 一，遍历只能是非叶子结
        // 点，所以边界值设置为adjustLength / 2。
        // 这样可以减少遍历的次数，也算是精确控制吧
        for (int counter = rootIndex;counter < adjustLength / 2;) {
            //2*rootIndex必然是它的左结点的序号
            // 并且是存在的，而2*rootIndex+1却
            // 未必存在。
            //因为adjustLength/2是非叶子结点的
            // 最大范围加一，所以其范围内的非叶子
            // 结点必然有叶子结点存在。因为2*rootIndex+1
            // 和2*rootIndex求余的结果是一样的，
            // 所以最后一个非叶子结点不一定有右孩
            // 子结点，因此如下所示。
            int leftChildIndex = 2 * counter + 1;
            int rightChildIndex = leftChildIndex + 1;
            int smallerPointer = leftChildIndex;
            //如果右孩子结点的值小于左孩子结点
            // ，那说明右孩子结点应该优先被交
            // 换，前提是存在可能的话。
            if (rightChildIndex < adjustLength && sourceArray[leftChildIndex] > sourceArray[rightChildIndex])
                smallerPointer = rightChildIndex;
            //因为是小根堆，所以只要父结点比
            // 较小的孩子结点大就应该交换。
            if (sourceArray[counter] > sourceArray[smallerPointer]) {
                int tempElement = sourceArray[counter];
                sourceArray[counter] = sourceArray[smallerPointer];
                sourceArray[smallerPointer] = tempElement;
                //此时应该把循环指针指向较小的子结点的位置
                counter = smallerPointer;
                //因为本次调整的前提是数组已经整体有序，所以在此只要不满足交换条件就不会发生交换了。
                int twoPower = 1;
                int stepTwoPower = twoPower;
                for (int counter0 = 0;counter0 < adjustLength;counter0++) {
                    System.out.print(sourceArray[counter0] + " ");
                    if ((counter0 + 1) % stepTwoPower == 0) {
                        twoPower *= 2;
                        stepTwoPower += twoPower;
                        System.out.println();
                    }
                }
                System.out.println("\n一次调整完毕");
                //一旦不满足if中的条件，就说明不再会发生
                // 交换了，因为本次调整是在已经被调整好的
                // 前提下的。这样也可以省去很多不必要的遍历。
            } else break;
        }
    }
}