求二叉树父节点索引的多种写法

我们都知道堆结构有一个有趣的特性：对于数组 a 的每个元素，总有 a[k] <= a[2*k+1] 以及 a[k] <= a[2*k+2]，假设 k 从 0 开始。
我们可以画出如下的二叉树，其中每个数字指的是元素的下标。

                               0

              1                                 2
			  
      3               4                5               6
	  
  7       8       9       10      11      12      13      14
  
15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

那么每个父节点的值都要比它的两个子节点小。

假设我们已经知道了子节点的下标，存在变量 pos 中，如果要求它父节点的下标，根据上面提到的堆的特性，可以将其减去一除以二之后取整，具体操作如下：

parentpos = int((pos - 1) / 2)
parentpos = (pos - 1) // 2

pos 为 29 或者 30 时 parentpos 都为 14

下面有另外两种写法：

parentpos = (pos - 1) >> 1

这个是针对二进制的右移一位运算，以数字 29 为例，其二进制为 11101，移位之后是 01110，也就是十进制的 14。以数字 28 为例，其二进制为 11100，移位之后也是 01110，十进制的 14。二进制决定奇偶数的最后一位在右移后直接消失，转换成十进制后的数也从类似2**2+2*3*+2**4变成了2**1+2**2+2**3的形式，前者正好可以写成后者乘二的结果。

下面分别用 timeit 模块在命令行模式下计算两种写法的运行效率：

C:\Users>python -m timeit "int((30 - 1) / 2)"
10000000 loops, best of 3: 0.134 usec per loop

C:\Users>python -m timeit "(30 - 1) >> 1"
100000000 loops, best of 3: 0.0107 usec per loop

C:\Users>python -m timeit "(30 - 1) // 2"
100000000 loops, best of 3: 0.0107 usec per loop

可以看到，采用 int 类型转换的写法会将运行时间从 0.0107 微妙增加到 0.134 微妙，是一个数量级的区别。