algorithm - HeapSort - 交换前排序

Question

我正在使用算法，特别是堆排序。据我了解，堆排序算法涉及通过首先将列表转换为最大堆来准备列表。

转动我的

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

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

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

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

Answer 1

使其成为堆后，不一定要按降序排序。

堆只要求每个节点都比其子节点更大（或更小，对于最小堆），但没有说明子节点的顺序，也没有说明不同级别的节点之间的关系（其中一个不是另一个，见5下文6）。这意味着这也是一个有效的堆：

     9
   /   \
  5     8
 / \   /
1   2 6

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

Answer 2

对于你的问题

当列表已经按降序排序时，为什么需要交换？

根据定义：堆数据结构是一棵完全二叉树，其根大于（或小于）其子级。

heapify() 函数保证堆的构建。在你的情况下，它碰巧是按降序排列的。另一种情况是在杜克林的回答中指出的，它不是按降序排列的。

在堆排序中，在第一次 heapify() 调用之后，我们只知道一件事。堆的根（数组中的第一个元素）是数组中的 Max 元素。因此，将其移动到它的位置（最后一个位置）并将数组大小减少 1 并对所有元素再次应用相同的步骤。

heapify() 操作将为 O(log n)，因此总复杂度为 O(n log n)

希望能帮助到你！