二叉堆的叶节点在数组中的下标为什么从[n/2]+1开始?《算法导论》里在堆排序那一章有一道证明题如下证明：数组表示存储n个元素的堆时,叶节点的下标分别是[n/2]+1,[n/2]+2,..n(此处[]指取下限[

Question

二叉堆的叶节点在数组中的下标为什么从[n/2]+1开始?
《算法导论》里在堆排序那一章有一道证明题如下
证明：数组表示存储n个元素的堆时,叶节点的下标分别是[n/2]+1,[n/2]+2,..n (此处[]指取下限[3/2] = 1)
我的疑问如下：
举例来讲,现在有8个节点,构成了一个二叉堆,
(1)
/ \
(2) (3)
/ \ / \
(4) (5) (6) (7)
/
(8)
即使如算法导论中的惯例,数组下标从1开始,何以见得,leaf node (8)的下标为8,但是按照算法导轮上的这道证明题的结论,叶节点(8)在数组里德下标应该是[n/2]+1= [8/2] + 1 = 5
究竟是怎么回事?是我的理解有偏差吗?
上述二叉堆并没有给出节点的值,括号里的数字是值数组里的index.

Answer 1

二叉堆一般用数组来表示.如果根节点在数组中的位置是1,第n个位置的子节点分别在2n和 2n+1.因此,第1个位置的子节点在2和3,第2个位置的子节点在4和5.以此类推.这种基于1的数组存储方式便于寻找父节点和子节点.-----------数组表示存储n个元素的堆时,叶节点的下标分别是[n/2]+1,[n/2]+2,..n (此处[]指取下限[3/2] = 1)
是你的理解出了问题：
leaf node (8)的下标为8,按照算法导轮上的这道证明题的结论,有8个节点的二叉堆,在数组里叶节点的下标应该是从 [n/2]+1= [8/2] + 1 = 5 起,一直到 8 .即5~8都是叶节点.