为什么在由数组实现的堆中,索引0未被使用？

Question

我正在学习数据结构,每个源都告诉我在实现堆时不要使用数组的索引0,而不给出任何解释原因.我在网上搜索,搜索了StackExchange,但找不到答案.

Answer 1

没有理由为什么在数组中实现的堆必须使索引0处的项不被使用.如果将根设置为0,则项目at array[index]的子项位于array[index*2+1]和array[index*2+2].节点at array[child]的父节点位于array[(child-1)/2].

让我们来看看.

                  root at 0       root at 1
Left child        index*2 + 1     index*2
Right child       index*2 + 2     index*2 + 1
Parent            (index-1)/2     index/2

因此,将根设置为0而不是1会花费额外的添加来查找左子项,并使用额外的减法来查找父项.

我看不到那些额外的指令在运行时间上有很大的不同.

我之所以认为从一个基于0的数组的语言开始1是错误的,请参阅/sf/answers/3486429341/和我的博客文章但这就是我们一直以来的方式!

Answer 2

正如我在CLRS书中发现的那样,在性能方面有一些意义,因为一般来说,班次操作员的工作速度非常快.

在大多数计算机上,LEFT过程可以2*i通过简单地将 i左边的二进制表示移位一位位置来计算一条指令.类似地,RIGHT过程可以通过将 i 的二进制表示移位一位位置然后加1作为低位来快速计算2*i+1.PARENT过程可以i/2通过向右移位一位位置来计算.

因此,在索引1处启动堆可能会更快地计算父,左和右子索引.

Answer 3

（在搜索过程中，我想出了自己的答案，但我不知道它是否正确。）

如果索引0用于根节点，则对其子节点的后续计算将无法进行，因为我们有indexOfLeftChild = indexOfParent * 2和indexOfRightChild = indexOfParent * 2 + 1。然而0 * 2 = 0和0 * 2 + 1 = 1，并不能代表我们想要的亲子关系。因此，我们必须从1让数组表示的树符合我们想要的数学属性开始。

Answer 4

正如 AnonJ 所观察到的，这是一个品味问题，而不是技术必要性。从 1 而不是 0 开始的一件好事是，在二进制字符串 x 和正整数之间存在双射，将二进制字符串 x 映射到以二进制写成 1x 的正整数。字符串 x 给出了从根到索引节点的路径，其中 0 表示“取左孩子”，1 表示“取右孩子”。

另一个考虑是，否则未使用的“第零”位置可以保存一个值减去无穷大的哨兵，在没有分支预测的架构上，这可能意味着运行时间的不可忽视的改进，因为在向上循环中只有一个测试而不是二。