看图聊算法:堆排序,我们学习它可能并不是为了排序

💡 原文中文,约5900字,阅读约需15分钟。
📝

内容提要

堆排序是一种利用完全二叉树和最大堆的排序算法,适用于优先队列等场景。它通过维护最大堆的特性来实现排序,步骤包括建立最大堆、交换最大元素、重建最大堆。堆排序在优先队列等领域发挥关键作用,优化版本是快速堆排序。学习堆排序涉及到其背后的意义和广泛应用。

🔎

延伸解读

堆排序的实战短板:缓存不友好

文章指出,堆排序在实际应用中往往不如快速排序高效,主要原因在于堆排序在数组中大范围跳跃访问,导致缓存命中率降低。而快速排序由于连续访问数据,更契合现代计算机的缓存系统。因此,尽管堆排序理论优雅,但在通用排序场景下并非首选,理解这一性能差异有助于在工程中做出合理选择。

优先队列:堆的真正用武之地

堆最常见的应用并非排序,而是实现优先队列。文章以从10亿个数中找出最小的100万个数为例,说明如何用最大堆高效解决:先读入前100万个数建堆,后续元素若小于堆顶则替换堆顶并调整。这种方法避免了全量排序的开销,体现了堆在资源有限时处理海量数据的优势。

快速堆排序的优化思路

针对传统堆排序效率不高的问题,文章介绍了一种改进方案:删除堆顶后,直接比较空缺位置的两个子堆首领,将较大者提升到空缺中,递归重复直至堆底。这样避免了将较小元素提升到堆顶再下沉的冗余比较。这种快速堆排序虽非完全原地,但每次提取排序项的效率更高,文章称其可能是最接近比较排序理论极限的算法。

❓

Q&A

堆排序为什么在实际中不如快速排序高效?

堆排序在数组中的大范围跳跃可能导致缓存命中率降低,而快速排序由于连续的数据访问模式,更适合现代计算机的缓存系统。

完全二叉树如何用数组表示?节点位置怎么计算?

完全二叉树可以将节点按顺序存放在数组中,根节点存放在数组的第1位置。对于任意位置i的节点,其父节点位置为i/2,左子节点位置为2*i,右子节点位置为2*i+1。

如何从一个随机数组构建最大堆?

从完全二叉树的最后一个父节点(位置为n/2)开始,自底向上地对每个父节点调用MAXHEAPIFY函数,逐步将任意数组转换为最大堆。

堆排序的具体步骤是什么?

堆排序的步骤包括:1. 建立最大堆;2. 将堆顶(最大元素)与最后一个元素交换;3. 排除最后一个元素,对剩余元素重建最大堆;4. 重复上述过程直到堆的大小为2。

如何用最大堆在10亿个数中找出最小的100万个数?

读取前100万个数构建最大堆。对于后续每个数,如果大于堆顶则忽略;如果小于堆顶,则移除堆顶并将新数加入堆中。最终堆中保留的就是最小的100万个数。

快速堆排序相比传统堆排序有什么改进?

快速堆排序在删除堆顶后,比较空缺位置正下方的两个子堆首领,将较大的那个提升到空缺中,递归重复直到堆底。这样避免了将小元素提升到堆顶再下沉的过程,减少了比较次数,效率更高。

🏷️

标签

➡️

继续阅读