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

Question

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

Answer 1

在数组中实现的堆没有理由必须让索引 0 处的项目未被使用。如果将根置于 0，则 array[index] 中的项目在 array[index*2+1] 和 array[index* 2+2]。 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 会花费额外的加法来找到左边的 child ，并需要额外的减法来找到父节点。

对于更一般的情况，它可能不是二叉堆，而是 3 堆、4 堆等，其中每个节点有 NUM_CHILDREN 个子节点而不是 2 个，公式为:

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

我看不出那些额外的指令对运行时间有多大影响。

关于为什么我认为在具有基于 0 的数组的语言中从 1 开始是错误的原因，请参阅 https://stackoverflow.com/a/49806133/56778和我的博文 But that's the way we've always done it!