我们今天刚在课堂上学习了Heap排序，我很困惑它是如何被认为如此高效的——IE有O(nlogn(。
- 它不节省内存，因为您必须构建一个表示整个数组的堆并不断修改它
- 它在计算上并不高效，因为你每次都必须找到最大值并将其带到根
我可能只是不太了解堆，但这似乎是一种非常迂回的选择排序方式，但不知何故，它被认为更有效。。。为什么会这样？
它不节省内存，因为您必须构建一个表示整个阵列的堆
；"中心把戏"；堆排序所基于的(如果没有它，它可能就不相关了(是，数组可以被堆在适当的位置(这可以在线性时间内完成(，然后堆一直保持在数组的开头，随着数组末尾排序项目范围的增加而锁步缩小。整个算法可以在没有分配和递归的情况下进行：O(1(内存开销。
它在计算上并不高效，因为每次都必须找到最大值并将其带到根。
没有搜索。任何项目都可以被放到根中；冒泡下来"；以恢复堆属性。最明显的选择是堆中的最后一项，它很难移除(它不会在堆中留下一个"洞"，只会将大小减小1(。它位于数组中要放置旧根值的同一位置，所以这个项目最好让开。