Chapter3: 更好的查找与排序算法
11. 堆的概念及堆排序
[1] 图解排序算法(三)之堆排序 讲得很好，这里相当于写个精简大纲版并将java代码转换为C++代码
堆的相关概念
堆排序概述
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆的概念
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
前面说了树是一种逻辑结构，可以用数组来存储，堆是一种特殊的树，自然也可以，如上面的大顶堆结点按照从上到下从左到右标号，然后存储到数组。
将这种逻辑结构映射到数组中就是下面这个样子：
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
**大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] **
**小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] **
堆排序的基本思想和步骤
堆排序的基本思想是：
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
堆排序代码实现
代码思想
0. 初始化条件
一个数组，可以认为它的逻辑结构是堆，编号从上到下从左到右，从0开始
1. 构建大顶堆
调整堆使得对于整棵树及所有子树都是父元素最大，其实就是
-
从倒数第一个非叶子结点开始，从下到上，从右到左遍历调整结构
for(int i=arrLen/2-1;i>=0;i--)叶子结点没有左右子树，所以无论是大顶堆还是小顶堆都可以可以认为它们满足条件
从下到上从右到左是堆的存储结构-数组的逆序
关于最后一个非叶子结点的下标：
完全二叉树中 n0=n2+1 (度为0的结点数=度为2的结点数+1)，如果完全二叉树中结点总数为奇数，则没有度为1的结点，如果结点总数为偶数，则有1个度为1的结点。而 n=n0+n1+n2 ，所以 n2=(n-n1-1)/2 , n2+n1=(n+n1-1)/2 ,如果结点总数是奇数，n1=0 ,非叶子结点数为 (n-1)/2, 考虑到计算机中的除法是向下取整的，所以对于奇数n而言，n/2==(n-1)/2，所以最后一个非叶子结点下标为 n/2-1 , 如果结点总数是偶数, n1=1 ,最后一个非叶子结点下标也是 n/2-1
还有1个注意点就是：
当数组下标从0开始时和从1开始时，树中父子结点的关系式是不一样的；n从0开始，左孩子结点和父结点的关系为 k=2*i+1 ,当n从1开始时，左孩子结点和父结点的关系为 k= i * 2;
- 对遍历到的每个元素调用调整堆结构的函数
adjustHeap(arr,i,arrLen);，即一次循环中调整以结点i作为根结点的子树(包括其所有子孙结点)使之满足堆的定义
2. 循环交换堆顶元素到数组末尾 & 调整堆结构
- 交换堆顶元素(最大值)与最后1个元素
- 调换元素后这棵树会不满足堆的定义，需要调整，此时调用堆调整函数
adjustHeap(arr,i,arrLen)即可，i固定为0，arrLen每次调换后要-1。 即每次调换后都要对整棵树的进行堆结构调整(不包括已排序的元素) - 循环进行上面两小步，将数组所有元素排好序
for(int j=arrLen-1;j>0;j--)
3.堆结构调整函数 adjustHeap(int* arr,int i,int arrLen)
- 函数参数分别为输入数组，要调整的结点，数组长度(用来确定边界)
- 函数功能为针对输入结点
i，调整以它作为根结点的子树使得满足堆的定义，如果i=0那就是对整棵树进行调整
代码
/*堆排序*/
void heapSort(int* arr,int arrLen){
//构建大顶堆
for(int i=arrLen/2-1;i>=0;i--){
//从第一个非叶子结点开始，从下到上，从右到左调整结构
//因为叶子结点没有子结点，可以认为每个叶子结点单独作为一棵子树已经是大顶堆/小顶堆
adjustHeap(arr,i,arrLen);
}
//循环 交换堆顶元素到数组末尾 & 调整堆结构
for(int j=arrLen-1;j>0;j--){
swap(arr,0,j);//将堆顶元素arr[0]与末尾元素arr[j]互换
adjustHeap(arr,0,j); //调整数组第一个元素到最后一个未排序元素(j的前一个元素)之间的堆
}
}
/*调整大顶堆(仅是调整过程，建立在大顶堆已构建的基础上)*/
void adjustHeap(int* arr,int i,int arrLen){
int tmp=arr[i];//保存当前元素i
for(int k=i*2+1;k<arrLen;k=k*2+1){//遍历左子树,下面第一个if判断会在合适的时候拐弯,注意当下标从1开始时，父子结点的关系式和下标从0开始时的关系式是不一样的
if(k+1<arrLen && arr[k]<arr[k+1]){//k的含义是上一个k的左结点，k>arrLen时,说明已经超越了树的范围，不存在这个结点；k+1=arrLen时,k为最左边的叶子结点，其右兄弟为已排序元素 & 左子结点小于右子结点
k++;//k指向右子结点
}
if(arr[k]>tmp){//如果子结点大于父结点，注意这里是用arr[k]与tmp比较而不是arr[i]，这就是下面只需要将子结点的值赋值给父结点，而不需要将父结点的值赋值给左结点的原因，父结点的值一直保存在tmp中，直到遍历到底层后(不会也不需遍历所有元素，只走不满足条件需要调整的路线)才将tmp的值赋给合适的元素
arr[i]=arr[k];//将子节点值赋给父结点(不用交换,在循环结束后直接赋值)
i=k; //将父元素指针移向它的左子树
}
/*下面这个if判断可以取代上面的if判断，不需要tmp了*/
// if(arr[k]>arr[i]){
// swap(arr,i,k);
// i=k;
// }
// else//不进行调换
// break;
}
arr[i]=tmp;//将tmp放到最终的位置
}
/*交换元素*/
void swap(int* arr,int a,int b){
int tmp=arr[a];
arr[a]=arr[b];
arr[b]=tmp;
}
时间复杂度分析
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为 O(n)，在交换并重建堆的过程中，需交换 n-1 次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1] 逐步递减，近似为 nlogn 。所以堆排序时间复杂度一般认为就是 O(nlogn) 级。
参考链接
[1] 图解排序算法(三)之堆排序
