问HeapSort -交换前排序

EN

使它成为一个堆后，它不一定按降序排序。

堆只要求每个节点比它的子节点更大(或更小，对于最小堆而言)，但是没有提到子节点的顺序，也没有提到不同级别的节点之间的关系(如果其中一个不是另一个的直接后代，请参见下面的5和6 )。这意味着这也是一个有效的堆：

     9
   /   \
  5     8
 / \   /
1   2 6

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

请回答你的问题

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

根据定义:堆数据结构是一个完整的二叉树，它的根大于(或小于)其子树的属性。

heapify()函数保证堆的构造。在你的例子中，它恰好是降序的。另一种情况是在对杜克灵的回答中指出的，这一问题并不是按下降的顺序进行的。

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

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

希望能帮上忙！