动画 | 什么是堆排序？

忘是亡心i 2023-06-22 10:25 5阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

来源 | 算法无遗策

回顾一下我们学过的 [选择排序][Link 1] ，在无序区找到一个最小（大）的元素需要比较n-1次，找到第二小的元素需要比较n-2次，直到最后比较1次。而堆排序因为二叉堆的性质，堆顶就是最大的元素，查找次数只有一次，但是将无序转成有序中间还需要一个预处理过程：构造堆有序。

堆有序并不代表数组有序，堆有序是满足 [二叉堆][Link 2] 性质的：

1.父节点的键值总是优先于任何一个子节点的键值；

2.左右子树都是一个二叉堆。

所以堆排序分为两个阶段，构造堆有序和下沉排序阶段。

构造堆有序阶段是将原始数据重新组织安排到一个二叉堆中，堆有序就是一棵二叉树的每个节点都优先于它的两个子节点，不代表数组有序；

下沉排序阶段是将二叉堆中取出优先级高的直至取出所有元素，得到数组有序结果。

构造堆有序的方式有两种，一种是上浮，另一种是下沉。这里以最大堆为例。

自低向上的堆有序化（上浮）

上浮是某节点与其父节点的比较，如果某节点比其父节点要大，就通过交换的方式进行修复堆。如果这个节点仍然比现在的父节点还大，可以通过循环的方式进行修复堆，直到遇到更大的父节点。

那从哪个节点开始呢？

如果从数组最后一个节点进行开始上浮操作，它的父节点和祖父节点大小关系是不确定的，如果它的祖父节点比它父节点小，并不能保证整个完全二叉树能够二叉堆化。

所以从根节点的左孩子开始进行，数组下标为1开始，进行自底向上的堆有序化。在循环进行比较的时候会发现，这个节点已经进行过修复堆了，所以当上浮操作不再交换的时候可以做一个标记，截止进行比较。

如果能够合理优化的话，在时间上的消耗有可能要比下沉阶段的还要少。

动画

Code

![format_png 1][]

Result

初始状态 \[13, 9, 15, 11, 3, 7, 17, 5, 1\]

交换 \[15, 9, 13, 11, 3, 7, 17, 5, 1\]

交换 \[15, 11, 13, 9, 3, 7, 17, 5, 1\]

交换 \[15, 11, 17, 9, 3, 7, 13, 5, 1\]

交换 \[17, 11, 15, 9, 3, 7, 13, 5, 1\]

\[17, 11, 15, 9, 3, 7, 13, 5, 1\]

自顶向下的堆有序化（下沉）

下沉是当前节点和左右孩子三者之中的比较，在整个进行自顶向下堆有序化的过程中，它是从非叶子节点开始的，即数组最后一个节点的父节点。

动画

Code

![format_png 2][]

Result

初始状态 \[13, 9, 15, 11, 3, 7, 17, 5, 1\]

交换 \[13, 9, 17, 11, 3, 7, 15, 5, 1\]

交换 \[13, 11, 17, 9, 3, 7, 15, 5, 1\]

交换 \[17, 11, 13, 9, 3, 7, 15, 5, 1\]

交换 \[17, 11, 15, 9, 3, 7, 13, 5, 1\]

\[17, 11, 15, 9, 3, 7, 13, 5, 1\]

下沉排序

堆排序的主要工作还是在第二阶段完成的，下沉排序。这里我们将堆中最大的元素取出，和数组最后一个元素做交换，数组可操作的长度也相应的缩小一个位置。然后从堆顶开始进行下沉操作，无论循环多次都是从堆顶开始，直到数组可操作的长度最后为1。

动画

Code

![format_png 3][]

Result

初始状态 \[13, 9, 15, 11, 3, 7, 17, 5, 1\]

堆有序化

交换 \[13, 9, 17, 11, 3, 7, 15, 5, 1\]

交换 \[13, 11, 17, 9, 3, 7, 15, 5, 1\]

交换 \[17, 11, 13, 9, 3, 7, 15, 5, 1\]

交换 \[17, 11, 15, 9, 3, 7, 13, 5, 1\]

下沉排序

交换 \[15, 11, 1, 9, 3, 7, 13, 5, 17\]

交换 \[15, 11, 13, 9, 3, 7, 1, 5, 17\]

交换 \[13, 11, 5, 9, 3, 7, 1, 15, 17\]

交换 \[13, 11, 7, 9, 3, 5, 1, 15, 17\]

交换 \[11, 1, 7, 9, 3, 5, 13, 15, 17\]

交换 \[11, 9, 7, 1, 3, 5, 13, 15, 17\]

交换 \[9, 5, 7, 1, 3, 11, 13, 15, 17\]

交换 \[7, 5, 3, 1, 9, 11, 13, 15, 17\]

交换 \[5, 1, 3, 7, 9, 11, 13, 15, 17\]

\[1, 3, 5, 7, 9, 11, 13, 15, 17\]

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 4][]

**戳一下下方的小程序，24 小时一起学算法**

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU3MDkxMDg2OA%3D%3D&chksm=fce97359cb9efa4fe0b1d14b688b350ad885403bffaa2b4160f8ae82b2727fe5abe4b4d8c8ad&idx=1&mid=2247484066&scene=21&sn=02737fcf186aba89d760ef5f88ab3a4b#wechat_redirect
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103545324
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbTdYaWJ6Ym9yNndLaWNpY2Z5aHdUTUxDNDJWTEdqQ3Q3TnQzMDZHZjlhcVlaSHJIaWF3Q3l2eVVqYXdoeGZWTGliaWNOUEdLaWNsRjY2UXplYlEvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbTdYaWJ6Ym9yNndLaWNpY2Z5aHdUTUxDNGh2U1ZGZklTaWJWcExvOFkzV2UwczBzaWJoRGFlZDVOVkVuaEFYSXd0VWdCYWZJZ25TUGljdG16Zy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbTdYaWJ6Ym9yNndLaWNpY2Z5aHdUTUxDNGdtdGpmR3p2SVRVRFFwcm0zVHFFVmxCMHhBd3VpYkM0aFc3bEtWcFhBQ0xkNlJOeWljMW4wOEtRLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png