堆排序是基于完全二叉樹實現(xiàn)的，在將一個數(shù)組調(diào)整成一個堆的時候，關(guān)鍵之一的是確定最后一個非葉子節(jié)點的序號，這個序號為n/2-1，n為數(shù)組的長度。但是為什么呢？

可以分兩種情形考慮：

①堆的最后一個非葉子節(jié)點若只有左孩子

②堆的最后一個非葉子節(jié)點有左右兩個孩子

完全二叉樹的性質(zhì)之一是：如果節(jié)點序號為i，在它的左孩子序號為2*i+1，右孩子序號為2*i+2。

?

對于①左孩子的序號為n-1，則n-1=2*i-1，推出i=n/2-1；

?

對于②左孩子的序號為n-2，在n-2=2*i-1，推出i=(n-1)/2-1；右孩子的序號為n-1，則n-1=2*i+2，推出i=(n-1)/2-1；

很顯然，當完全二叉樹最后一個節(jié)點是其父節(jié)點的左孩子時，樹的節(jié)點數(shù)為偶數(shù)；當完全二叉樹最后一個節(jié)點是其父節(jié)點的右孩子時，樹的節(jié)點數(shù)為奇數(shù)。

根據(jù)java語法的特征，整數(shù)除不盡時向下取整，則若n為奇數(shù)時(n-1)/2-1=n/2-1。

因此對于②最后一個非葉子節(jié)點的序號也是n/2-1。

得證。

顯然序號是從0開始的。

from：https://www.cnblogs.com/malw/p/10542557.html