堆排序详解

堆的简述

• 堆是一种完全二叉树，并且满足：
  1. 大根堆每个节点上的值大于等于它左右两个节点上的值
  2. 小根堆每个节点上的值小于等于它左右两个节点上的值
     

堆排序概述

• 堆排序顾名思义，是使用“堆”这种数据结构的思想，快速地访问数组中最大的元素，并且以类似二分的方式维护最大值的一种排序方式
• 堆排序并非使用了堆这个数据结构，而是使用数组来实现，用下标来维护对应二叉树的性质

堆排序的树状结构

下标访问的前提准备

• 前面我们提到，堆排序使用数组模拟出二叉树的效果，那么我们必须拥有能通过父节点快速访问它的两个子节点的手段，由于我们是访问下标，所以需要通过下标来访问

具体公式如下：
l c h i l d = f a t h e r ∗ 2 + 1 lchild = father * 2 + 1lchild=father∗2+1
r c h i l d = f a t h e r ∗ 2 + 2 rchild = father * 2 + 2rchild=father∗2+2

• 具体推导见下：
  

建堆过程

• 由于前面给出了父子节点之间的下标关系，所以我们可以用二叉树的性质对它进行操作
• 第一步我们应该先把这个数组调整成一个堆的形式，这时候就要用到向下调整
• 也就是说，在原本的数组中，如果将下标0节点看作根节点，如果直接将整个数组当作大根堆来使用，可能会出现父节点小于子节点的情况，所以要从下向上的，让每一层的子树都能够满足大根堆的性质

排序与调整过程

• 上一步我们已经将数组调整成一个最大堆，也就是说数组下标为0的数已经是最大值了。
• 这一步，为了排序我们需要将最前面的数取出来，但是为了根节点0下标处有值，于是我们可以选择将0节点与当前堆的最后一个数交换，然后由于取出来了一个数，将数组大小缩小1
• 此时的最大值也恰好来到了最后一个元素的位置，反复进行之后数组自然而然完成了从小到大的排序

堆排序的具体实现

• 根据上面所说的几个需求，我们写出对应的函数，最终拼装在一起就是最终的排序函数

交换函数

• 这个函数我们希望交换数组的两个值，直接写成传地址的函数，对地址直接修改】

voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}

调整堆结构函数

• 详细解释放在注释中

voidhepify(int*nums,intsize,inttar){//这里的nums是待排序数组，size是逻辑上的堆排序长度，tar是待调整的子树的根节点下标intlchild=tar*2+1;// 左子节点下标intright=tar*2+2;//右子节点下标intmax=tar;//记录一下左右子节点中有可能的最大值的下标if(lchild<size&&nums[lchild]>nums[max]){max=lchild;//如果该节点拥有子节点并且这个字节点的值比当前的max大时，就更新max为这个值}if(rchild<size&&nums[rchild]>nums[max]){max=rchild;//同理，如果右子节点存在并且值大于当前被更新过的最大值下标的对应值的时候更新最大值为右子节点}if(max!=tar){//这一步是判断左右子结点中是否有比父节点大的值存在，如果有，那么上面的两个if语句会更新max让其不等于tar，进入之后先交换父节点与该节点swap(&nums[max],&nums[tar]);//此时逻辑上的父节点已经被更新为了两个子节点中的较大值，并且父节点也被调整到了子结点上heapify(max);//但是由于被调整下去的父节点也会作为别人的父节点继续干扰大根堆的性质，所以还得对被调整下去的节点进行第二次调整，此时我们就可以递归地调用函数，直到最后的节点符合堆的性质或者说没有子节点为止}}

调用堆调整的排序主函数

• 先在原数组的基础上建堆
• 对一个建好的堆，和刚刚说的一样，要将它的0下标数与当前堆的最后一个数交换，然后长度减一

最后一个有子节点的父节点的下标关系

• 前面提到过需要先找到最后一个有子节点的父节点的下标，然后从这个下标开始，逐个向前进行调整
• 我们前面推到过，

l c h i l d = f a t h e r ∗ 2 + 1 lchild = father * 2 + 1lchild=father∗2+1
r c h i l d = f a t h e r ∗ 2 + 2 rchild = father * 2 + 2rchild=father∗2+2

• 如果将lchild或者rchild减一再除以二
• 就会得到：

f a t h e r 和 f a t h e r + 0.5 father 和 father + 0.5father和father+0.5

• 由于整数除法直接作截断，所以无论左右子节点减一再除以二都能得到父节点的下标，即：

f a t h e r = ( l c h i l d − 1 ) / 2 = ( r c h i l d − 1 ) / 2 father = (lchild - 1) / 2 = (rchild - 1) / 2father=(lchild−1)/2=(rchild−1)/2

• 并且由于数组0下标也会有数，所以要在左右子节点下标基础上减一，也就是
  ( c h i l d − 2 ) / 2 (child - 2) / 2(child−2)/2
• 这就是调整堆结构时的起始下标

voidheapSort(int*nums,intsize){for(inti=size/2-1;i>=0;i--){//从第一个父节点开始向上挨个调整为堆结构heapify(nums,size,i);}for(inti=n-1;i>=0;i--){//从数组最后一个数的下标开始，将最后一位和0下标处交换，然后缩小数组大小（i—-）swap(&nums[0],&nums[i]);heapify(nums,i,0);//每次交换之后根节点变成最小值，不符合最大堆结构，所以要再对数组第一个数进行排序//由于数组大小在逻辑上一经减一了，所以要传入此时i即为数组大小}}

小结

• 堆排序是一种利用数组搭建在逻辑上满足堆性质，从而快速访问最大最小值的排序方式
• 堆排序实质上是一种被优化过的插入排序，时间复杂度也降低到了O ( N l o g N ) O(NlogN)O(NlogN)，与归并排序，快速排序一同在实践中大量使用