原地堆排序只能用最大堆的思想吗？可以使用最小堆？

Answer 1

liuyubobobo 2019-10-30 15:49:30

不可以，或者更准确的说，会极度地不方便。

因为我们使用数组表示堆的时候，堆顶索引是 0。后续关于一个节点的相邻节点是 2*i + 1 和 2*i + 2，是基于这一假设的。否则，我们没有统一的找到一个节点的左右孩子节点的方式。

当使用最大堆的时候，每次将最大元素放到最后，不会破坏在前面的数组中，将它看做一个堆，堆顶元素依然索引为 0 的性质。

你可以尝试使用最小堆的思想实现一下试试看？看看会遇到什么问题？

继续加油！：）

• 提问者 weixin_慕妹5444478 #1

  非常感谢