Max Heapify-伪代码

Question

我对最大堆排序伪代码的一部分感到困惑。 降到 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)

Answer 1

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

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

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

Answer 2

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

这几乎类似于 selection 排序（我们将 select A[1..i] 中的最大元素并将其与 A[i] 交换），除了堆排序A[1..i] 使用称为 maxheap 的数据结构存储，因此 selecting 最大元素的过程不是使用线性搜索（如 selection 排序）而是通过maxheapifying 数组，从而将最大的元素带到第一个位置 A[1]。因此，找到最大的元素需要 log n 时间而不是线性时间。

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

Max Heapify-伪代码

Max Heapify-pseudocode

algorithm

language-agnostic

heapsort

max-heap