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

103

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

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

可以分两种情况考虑:

  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