algorithm - HeapSort - 在交换之前排序

Question

我正在研究算法，特别是堆排序。根据我的理解，heapsort 算法涉及通过首先将列表转换为最大堆来准备列表。

转动我的

[2, 8, 5, 3, 9, 1]

进入
[9, 8, 5, 3, 2, 1]

对于堆排序，我应该将 9 与 1 交换。但是通过在最大堆之后直接查看数组，我看到一个按降序排列的排序列表。为什么当列表已经按降序排序时需要交换？

这只是我看完之后的想法: https://www.youtube.com/watch?v=2DmK_H7IdTo

Answer 1

做成堆后，不一定是降序排列

堆只要求每个节点都比它的子节点大(或小，对于最小堆)，但没有说明子节点的顺序，也没有说明不同级别节点的关系(其中一个不是另一个的直接后代，请参阅下面的 5 和 6)。这意味着这也是一个有效的堆:

     9
   /   \
  5     8
 / \   /
1   2 6

[9, 5, 8, 1, 2, 6]