【数据结构：排序算法】堆排序（图文详解）

🎁个人主页：我们的五年

🔍系列专栏：数据结构课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

目录

🍩1.大堆和小堆

🍩2.向上调整算法建堆和向下调整算法建堆：

🍟向上调整算法：

🍟向下调整算法：

🍟用这两种方法建堆的时间复杂度：

🍩3.堆排序：

---

 

🍩1.大堆和小堆

要想弄明白堆排序，我们先来看看大堆和小堆的概念和区别： 

注意：堆是完全二叉树。

大堆：父节点都大于孩子节点。

小堆：父节点都小于孩子节点。

🍩2.向上调整算法建堆和向下调整算法建堆：

注：根节点我定为0

🍟向上调整算法：

向下调整算法调整该节点的前提是该节点以上的树已经是堆（大堆或者小堆），但是开始的时候，树里面的元素是随便放置的，但是可以把根元素以上看成一个堆，然后向上调整从2*0+1（第二层左边的元素）的位置开始就可以了。

---

以向上调整建立大堆为例：

从已经建好的堆的下一层开始向上调整，这里可以把根看成小堆，要想把整个二叉树调整为小堆形式，我们就要从根的下一层，把每个元素都进行一次向上调整。

向上调整的实现：

根该节点开始，我们把该节点与它的父节点进行比较，因为该节点以上的节点已经是大堆，此时的根是该树最大元素，所以只要和根比较谁大，如果比根大就交换位置，这样增加一个元素以后，该树还是大堆。

从上面图来看，向上调整结束的条件为该节点到达根节点，上面没有元素了。

由孩子节点的下标找到父节点的下标是：parent=（child-1）/2。

实现代码：

void AdjustUp(int* a,int child)
{//该节点开始比较int parent = (child - 1 - 1) / 2;while (child > 0)	//当节点到达根节点，就没有父亲节点了，就停止{if (a[parent] < a[child]){int tmp = a[parent];a[parent] = a[child];a[child] = a[parent];child = parent;parent = (child - 1 - 1) / 2;}else{break;}}
}

🍟向下调整算法：

向下调整算法的要求就是左右子树已经是堆（大堆或者小堆）。结束的条件是孩子节点为NULL。

代码为：
 

void AdjustDown(int* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1]>a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

🍟用这两种方法建堆的时间复杂度：

假如待排序的二叉树有K层，假设为满二叉树：
如果用向上调整算法，那么进行的次数是：

第1层：2^0*0        //2的0次方这这一层的节点个数，0是调整的次数，根节点向上调整的时候 ，不需要调整。

第2层：2^1*1

……

第K层：2^(k-1)*k-1

所以总的次数为：

2^0*0+2^1*1+2^2*2+……+2^(k-1)*k=(k-1)*2^k-2.

个数N=2^k-1.k=log2 (N+1)

所以O（N）=(log2 (N+1)-1)*(N+1)-2。

数量级在log N

所以O（N）=N*log N。

向下调整：

其实用向下，就可以让节点最多的调整次数最少，也就是：多*少，少*多。

而向上调整，就是：多*多，少*少。第一层的节点少，不用调整，第二层两个节点，每个调整一次，后面节点多，每个节点调整次数也多。

第k-1层：2^(k-2)*1。

第k-2层：2^(k-3)*2。

……

第2层2^1*(k-2）。

第1层2^0*(k-1)。

总的：2^0*(k-1)+2^1*(k-2)+……+2^(k-2)*1=2^k+2*k-4。

O（N）=log N。

根据上面的结论，我们知道如果要建堆，那肯定是用向下调整更好。

🍩3.堆排序：

用向下排序拍好序以后，如果我们要排升序，我们就建大堆，如果我们要排降序，我们就排小队堆。

升序：大堆。

降序：小堆。

我们以升序为例：

当得到大堆的时候，根节点是最大的，然后我们把根节点和最后的节点换一下位置，这样最大的就到最后面去了，然后我们换完以后，又用向下调整使除最后一个节点以外为大堆，这样我们取根节点，我们就的得到了第二大的，我们就把第二大的和数组的倒数第2的位置换位置，然后再让根节点向下调整建立大堆……

这样我们就能让数组升序,代码实现：

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void AdjustDown(int* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1]>a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//升序
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}