algorithm - Max Heapify-伪代码

Question

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

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

Answer 1

堆排序本质上是选择排序，但数组中未排序的部分以 maxheap 数据结构的形式存储。更具体地说，堆排序的工作原理如下。首先选择数组 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。

Answer 2

这意味着您对 i in 的每个值重复该块{length[A], length[A] - 1, length[A] - 2, ..., 2}。

如果这是 C（或 C++，或 Java——所有的语法都一样），可以这样写：

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