堆排序

堆排序

堆排序的核心思想：借助堆数据结构，不断输出当前堆顶元素，每次堆顶离开当前堆后，对剩余元素重新调整成堆，直到堆中只剩下一个元素；元素的输出序列可转换成元素的有序序列

思路：

1、 我们以最大堆为例，在原数组上把元素按从小到大排序

2、 我们先对无序的数组初始化；即调整成最大堆；

2.1、无序的数组初始化最大堆思路：假设堆从root到叶子下标从0开始，它有一个性质：即int i = （最后一个叶子节点下标 / 2) 得到第一个子树，我们把它向下调整成最大堆，然后i--,把以i为下标的子树调整成最大堆…直到root

3、交换arr[0]和arr[length - 1] , 把剩余的元素调整成最大堆

4、(length-1)-- ; 循环调用步骤3-4，直到还剩下一个元素

请看图

好了，知道了思路我们来实现一下

void heapSort(int arr[] , int length ){
    //1、先调成最大堆
    for(int i = (length - 1) / 2; i >= 0 ; i--){
        _shiftDown(arr , length , i);
    }
    //2、堆排序
    for(int i = length - 1 ; i > 0 ; i--){
        swap(arr[i] , arr[0]);
        _shiftDown(arr , i , 0);
    }

}

向下调整

向下调整思路：

前提：堆结构中，只有要调整的那个元素，不满足最大堆结构

1、 以上图为例，index = 0(要调整的元素) ,我们先确定它是否有左孩子，有左孩子则继续；否则退出

2、 我们把要调整的元素和两个孩子中最大的那个比较，如果要调整的元素值大，则返回；否则交换要调整的元素和子孩子中大的那一个，更新index；循环调用1-2

void _shiftDown(int arr[] , int length , int index){
    //要确保以index为根的完全二叉树有左孩子才能向下调整
    while( 2 * index + 1 < length ){
        int j = 2 * index + 1;
        
        //因为是最大堆，我们要和子孩子中最大的一个交换值
        if(j + 1 < length && arr[j + 1] > arr[j]){
            j = j + 1;
        }
        
       //如果最大的子孩子不大于它的父亲的值，则终止循环
        if(arr[index] >= arr[j]){
            break;
        }
        //否则，交换值，更新下标，继续向下调整
        swap(arr[index] , arr[j]);
        index = j;
    }

}

注：
1、因为堆的结构是完全二叉树，因此可以用数组的结构来存储(看图)

2、初始化数组时，为什么不直接从root开始?
因为我们不能保证root的左右两个子树满足最大堆结构，堆排序的前提：堆结构中，只有要调整的那个元素，不满足最大堆结构

3、 为什么向下调整用while循环，因为我们也不知道循环多少次
4、 swap函数是c++自带的