最大堆调整-伪代码

Question

我对Max Heap Sort的伪代码中有一部分感到困惑。 down to 2是什么意思？

HeapSort(A)
Build-Max-Heap(A)
for i <-- length[A] <b><i>down to 2</i></b>
do exchange A[1] <---> A[i]
heap-size[A] =  heap-size[A] -1
Max-Heapify(A,1)

- user7941837

Answer 1

这意味着你要针对{length[A]，length[A]-1，length[A]-2，...，2}中的每个i值重复执行该块。

如果这是C语言（或C++、Java——这些语言的语法都相同），可以这样写：

for (int i = length(A), i >= 2, i--) {
    do...
}

- Arya McCarthy

Answer 2

堆排序本质上是选择排序，但未排序的数组部分以最大堆数据结构的形式存储。更具体地说，堆排序的工作方式如下。首先选择数组A [1..n]中的最大元素，并将其与A [n]交换。然后选择数组A [1..n-1]中的最大元素，并将其与A [n-1]交换。重复此过程，直到在最后一次迭代中，我们发现A [1..2]中的最大元素并将其与A [2]交换。此时，元素A [2..n]处于正确的位置，因此A [1]也处于正确的位置，数组已排序。

这几乎就像选择排序（在其中我们将从A [1..i]中选择最大元素并将其与A [i]交换），只是在堆排序中，A [1..i]使用称为最大堆的数据结构存储，因此选择最大元素的过程不是使用线性搜索（如选择排序中那样），而是通过使数组成为最大堆并将最大元素带到第一个位置A [1]。因此，找到最大元素需要log n时间而不是线性时间。

以上算法可以表述为：对于 i=n, n-1, ..., 2（按此顺序），在 A[1..i] 中找到最大的元素并将其与 A[i] 交换。由于 i 按这种递减顺序取值，因此 for 循环可以写为：for i = n downto 2。

- Ashwin Ganesan