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。