堆排序（完全二叉树）最后一个非叶子节点的序号是-n-2-1-的原因

100

参考并修正了其中的错误：https://www.cnblogs.com/malw/p/10542557.html

堆排序是基于完全二叉树实现的，在将一个数组调整成一个堆的时候，关键之一的是确定最后一个非叶子节点的序号，这个序号为 n/2-1，n 为数组的长度。但是为什么呢？

可以分两种情况考虑：

  1. 堆的最后一个非叶子节点只有左孩子
  2. 堆的最后一个非叶子节点有左右两个孩子

完全二叉树的性质之一是：如果节点序号为 i，则它的左孩子序号为 2*i+1，右孩子序号为 2*i+2。

  1. 对于 情况1 左孩子(最后一个元素)的序号为 n-1，则 n-1=2*i+1，推出 i=n/2-1；
  2. 对于 情况2 左孩子(倒数第二个元素)的序号为 n-2，则 n-2=2*i+1，推出 i=(n-1)/2-1；右孩子(最后一个元素)的序号为 n-1，则 n-1=2*i+2，推出（这里跟左孩子推出的一样） i=(n-1)/2-1；

很显然，当完全二叉树最后一个节点是其父节点的左孩子时，树的节点数（数组元素数）为偶数；当完全二叉树最后一个节点是其父节点的右孩子时（满二叉树），树的节点数（数组元素数）为奇数。

根据一般编程语言的特性，整数除不尽时向下取整，则若 n 为奇数时 (n-1)/2-1=n/2-1。

因此对于 情况2 最后一个非叶子节点的序号也是 n/2-1。