为什么在由数组实现的堆中未使用索引0？ [英] Why in a heap implemented by array the index 0 is left unused?

问题描述

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

I'm learning data structures and every source tells me not to use index 0 of the array while implementing heap, without giving any explanation why. I searched the web, searched StackExchange, and couldn't find an answer.

推荐答案

没有理由在数组必须保留索引0处的项目未使用。如果将根设为0，则 array [index] 的项的子项位于 array [index * 2 + 1] 和 array [index * 2 + 2] 。 array [child] 的节点的父节点在 array [（child-1）/ 2] 处。

There's no reason why a heap implemented in an array has to leave the item at index 0 unused. If you put the root at 0, then the item at array[index] has its children at array[index*2+1] and array[index*2+2]. The node at array[child] has its parent at 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会增加一个额外的费用来找到左子，并另外减去它的父母。

So having the root at 0 rather than at 1 costs you an extra add to find the left child, and an extra subtraction to find the parent.

在更一般的情况下，它可能不是二进制堆，而是3堆，4堆等，每个节点有NUM_CHILDREN个子代，而不是2个公式是：

For a more general case where it may not be a binary heap, but a 3-heap, 4-heap, etc where there are NUM_CHILDREN children for each node instead of 2 the formulas are:

                  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

我看不到这些额外的指令对运行时间有很大的影响。

I can't see those few extra instructions making much of a difference in the run time.

原因以一种基于0的数组的语言从1开始是错误的，请参阅 https://stackoverflow.com/a/49806133/56778 和我的博客文章但这就是我们一直做到的方式！

For reasons why I think it's wrong to start at 1 in a language that has 0-based arrays, see https://stackoverflow.com/a/49806133/56778 and my blog post But that's the way we've always done it!

这篇关于为什么在由数组实现的堆中未使用索引0？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！