Heapsort - 为什么PercolateDown（）中的循环迭代（长度/ 2）次？

Question

Here we see a function PercolateDown() implemented in C++.

我只是不明白为什么循环结束，长度/ 2倍？

Moreover, Why the loop in build heap starts at n/2?

Answer 1

当你创建最大/最小堆，你不需要heapify（PercolateDown）的叶子，因为他们不可能有哪个是大/小那么他们的父母的子女。

Answer 2

请注意，在教科书C++源代码使用基于1的索引，即 array[0]不使用，array[n]应该是有效的参考成阵列数据。

这就是而不是符合C++标准约定（数组，矢量等与零基索引0 ... n-1）。

为了说明（1型）索引号（不是值）堆内：

  1 
    2  3 
    4 5 6 7 
8 9 10 

如果你读通过仔细你的链接中的文字，你会看到，在位置每一父节点i只有在这些位置不超过数组长度的情况下，堆中才有儿童2*i和2*i+1。

由于PercolateDown（）算法将父母与子女交换，因此只需要length/2迭代。

此外，堆是从下到上构建的。因此，迭代开始于n/2上升，即朝向位置1。