堆排序

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

归纳出堆排序算法的步骤：

1. 把无序数组构建成二叉堆。 2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

堆结构

堆是具有以下性质的完全二叉树：

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

对堆中的结点按层进行编号，将这种逻辑结构映射到数组中如下：

该数组从逻辑上讲就是一个堆结构，用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

1、算法描述

1、将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

2、将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

3、由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

算法图解

当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。

                                

上图所示，当我们删除值为10的堆顶节点，经过调节，值为9的新节点就会顶替上来；当我们删除值为9的堆顶节点，经过调节，值为8的新节点就会顶替上来.......

由于二叉堆的这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合，过程如下：

删除节点9，节点8成为新堆顶：

                                

删除节点8，节点7成为新堆顶：

                               

删除节点7，节点6成为新堆顶：

                               

删除节点6，节点5成为新堆顶：

                                     

删除节点5，节点4成为新堆顶：

                                   

删除节点4，节点3成为新堆顶：

                                 

删除节点3，节点2成为新堆顶：

                                      

原本的最大堆已经变成了一个从小到大的有序集合。

二叉堆实际存储在数组当中，数组中的元素排列如下：

  2、算法分析

（1）算法复杂度

堆排序的时间复杂度，主要在初始化堆过程和每次选取最大数后重新建堆的过程；

初始化建堆过程时间：O(nlog2n)

最好、最坏平均情况都需要循环建堆，更改堆元素后重建堆时间：O(nlog2n)

堆排序的时间复杂度为：O(nlog2n)

堆排序就是选择排序，空间复杂度为常数：O(1)

（2）算法稳定性（不稳定）

堆的结构是节点i的孩子为2 * i和2 * i + 1节点，

大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没有交换，那这2个相同的元素之间的稳定性就被破坏了。堆排序是不稳定的排序算法。

3、算法实现

#include<iostream> using namespace std; void downAdjust(int* arr, int parentIndex, int len) { int tmp = arr[parentIndex];//tmp保存父节点值，用于最后的赋值 int childIndex = 2 * parentIndex + 1; while (childIndex < len) { //有 右孩子，并且右孩子大于左孩子，定位到右孩子 左+1=右 if (childIndex + 1 < len && arr[childIndex + 1] > arr[childIndex]) { childIndex++; } if (tmp >= arr[childIndex])//如果父节点大于任何一个孩子值，跳出循环 { break; } // tmp < arr[childIndex] 单向赋值 arr[parentIndex] = arr[childIndex]; parentIndex = childIndex;//步进，父下标为原来孩子下下标 childIndex = 2 * childIndex + 1; //孩子下标也往下走 } arr[parentIndex] = tmp;//跳出循环后，父已经成了子节点，这时需要把 tmp赋值给此时的父 } void heapSort(int* arr, int len) { for (int i = (len - 2) / 2; i >= 0; i--) { downAdjust(arr, i, len);//将无序数组构建出成大顶堆 } for (int i = len - 1; i > 0; i--)//将堆顶元素与队尾元素交换，调整产生新的堆顶 { int tmp = arr[i]; arr[i] = arr[0]; arr[0] = tmp; downAdjust(arr, 0, i);//重新调整，此时长度恰好为 i ,很巧妙 } } void show(int* arr, int len) { for (int i = 0; i<len; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int arr[] = { 3,4,5,6,7,8,9,2 }; int len = sizeof(arr) / sizeof(arr[0]); show(arr, len); heapSort(arr, len); show(arr, len); return 0; }

打印：

原文参考：https://blog.csdn.net/free377096858/article/details/90482650