堆排序

堆排序是利用二叉堆的特性完成的排序。

二叉堆的特性

1. 最大堆的堆顶是整个堆中最大的元素
2. 最小堆的堆顶是整个堆中最小的元素

• 以最大堆为例，如果删除一个最大堆的堆顶(并不是完全删除，而是跟末尾节点交换位置，然后退出堆)，经过自我调整，第二大的元素就会成为堆顶元素，往复 n-1次即可完成排序

思路

1. 把无序数组构建成二叉堆。需要从小到大排序，则构成最大堆；反之，构成最小堆。
2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶

实现

//下沉调整堆
public static void downAdjust(int[] array, int parentIndex, int length){
    int temp = array[parentIndex];
    int childIndex = 2 * parentIndex + 1;
    while(childIndex < length){
    //如果有右孩子，且右孩子的值大于左孩子，则定位到右孩子
        if(childIndex+1 < length && array[childIndex+1] > array[childIndex])
            childIndex++;

    //如果父节点小于任何一个孩子的值，则直接跳出
        if(temp >= array[childIndex])
            break;
        //无须真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * childIndex + 1;
    }

    array[parentIndex] = temp;
}

//堆排序(升序)
public static void heapSort(int[] array){
    //1.将无序数组建成最大堆
    for(int i = array.length/2; i >=0; i--)
        downAdjust(array,i,array.length-1);
    
    //2.循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶
    for(int i = array.length-1; i > 0; i--){
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        //由于第一次的调整建成了最大堆，所以堆顶的左右孩子只比最大的元素小，
        //因而只需将堆顶的元素下沉即可重新得到最大堆，参照堆的删除节点操作
        downAdjust(array, 0 ,i);
    }
}

时间复杂度

下沉调整的空间复杂度为O(logn)，需要调整n次，因此时间复杂度为O(nlogn)

• 构建堆的时间复杂度为O(n)，而不是(nlogn)
• 堆的插入和删除的时间复杂度都是O(logn)