HeapSort - 在交换之前排序
HeapSort - Sorted before swapping
我正在研究算法，特别是堆排序。根据我的理解，heapsort 算法涉及通过首先将列表转换为最大堆来准备列表。
转动我的
[2, 8, 5, 3, 9, 1]
进入
[9、8、5、3、2、1]
对于堆排序，我应该将 9 与 1 交换。但是通过在最大堆之后直接查看数组，我看到一个按降序排列的排序列表。为什么当列表已经按降序排序时需要交换？
这只是我看完之后的想法：
https://www.youtube.com/watch?v=2DmK_H7IdTo
做成堆后，不一定是降序排列。
堆只要求每个节点都比它的子节点大（或小，对于最小堆），但没有说明子节点的顺序，也没有说明不同级别节点的关系（一个不是' t 是另一个的直系后裔，请参阅下面的 5 和 6）。这意味着这也是一个有效的堆：
9
/ \
5 8
/ \ /
1 2 6
[9, 5, 8, 1, 2, 6]
针对您的问题
Why is swapping required when the list is already sorted in decreasing order?
根据定义：堆数据结构是一个完整的二叉树，属性它的根大于（或小于）它的子节点。
heapify()函数保证堆的构建。在您的情况下，它恰好是按降序排列的。另一种情况在Dukeling的回答中指出，不是降序排列。
在堆排序中，在第一次 heapify() 调用之后，我们只知道一件事。堆的根（数组中的第一个元素）是数组中的最大元素。因此，将它移动到它的位置（最后一个位置）并将数组大小减少 1，并对所有元素再次应用相同的步骤。
heapify() 操作的复杂度为 O(log n)，因此总复杂度为 O(n log n)
希望对您有所帮助！
我正在研究算法，特别是堆排序。根据我的理解，heapsort 算法涉及通过首先将列表转换为最大堆来准备列表。
转动我的
[2, 8, 5, 3, 9, 1]
进入
[9、8、5、3、2、1]
对于堆排序，我应该将 9 与 1 交换。但是通过在最大堆之后直接查看数组，我看到一个按降序排列的排序列表。为什么当列表已经按降序排序时需要交换？
这只是我看完之后的想法： https://www.youtube.com/watch?v=2DmK_H7IdTo
做成堆后，不一定是降序排列。
堆只要求每个节点都比它的子节点大（或小，对于最小堆），但没有说明子节点的顺序，也没有说明不同级别节点的关系（一个不是' t 是另一个的直系后裔，请参阅下面的 5 和 6）。这意味着这也是一个有效的堆：
9
/ \
5 8
/ \ /
1 2 6
[9, 5, 8, 1, 2, 6]
针对您的问题
Why is swapping required when the list is already sorted in decreasing order?
根据定义：堆数据结构是一个完整的二叉树，属性它的根大于（或小于）它的子节点。
heapify()函数保证堆的构建。在您的情况下，它恰好是按降序排列的。另一种情况在Dukeling的回答中指出，不是降序排列。
在堆排序中，在第一次 heapify() 调用之后，我们只知道一件事。堆的根（数组中的第一个元素）是数组中的最大元素。因此，将它移动到它的位置（最后一个位置）并将数组大小减少 1，并对所有元素再次应用相同的步骤。
heapify() 操作的复杂度为 O(log n)，因此总复杂度为 O(n log n)
希望对您有所帮助！