c–在arr[0]处使用root的二进制堆有什么好处？

我正在数组arr上写一个二进制堆.

除叶节点之外的每个节点都有两个子节点.

根可以是arr [0]或arr [1].

在Why in a heap implemented by array the index 0 is left unused?接受的答案说arr [1]更快.

但是在该答案下面的一条评论说,大多数实施都是在arr [0].

将根置于arr [0]有什么好处？

解决方法:

我是回答你关联的问题的人.

在具有基于0的数组的语言中创建具有arr [1]根的二进制堆是愚蠢的.不是因为它浪费了大量的空间,而是因为它造成了不必要的混乱代码而没有任何好处.

为什么代码混乱？因为它破坏了我们作为程序员多年来一直工作的基本规则：数组从0开始.如果你想要一个包含100个项目的数组,你就这样声明：

int a[100];


除了二进制堆.因为在1973年将一些原始二进制堆代码从Algol(其数组基于1)转换为C(基于0的数组)的白痴没有改变子计算和父计算的大脑,我们最终得到了在这一个特殊情况下,您需要分配101个项目：

int a[101];


当有人在不一致的情况下打电话给那个人时,他想出了一个似是而非的表演论点.

是的,在计算左子索引的代码中有一个额外的增量指令,在计运算符的父索引时有一个额外的减量指令.在二进制堆的更广泛的上下文中,这两个指令对使用堆的任何程序的运行时间没有实际的区别.没有.如果差异是可测量的,那肯定会有噪音.您的计算机上还有许多其他事情会对您的程序性能产生更大的影响.

如果您正在编写需要高性能优先级队列的程序,那么您首先要使用二进制堆做什么？如果你真的要在你的优先级队列中存储大量的东西,你可能应该使用像Pairing堆这样的东西,它会胜过二进制堆,虽然内存成本更高.

C STL priority_queue,Java PriorityQueue和python的heapq都使用基于0的二进制堆.编写这些包的人了解性能方面的考虑因素.如果使用基于1的二进制堆获得显着的性能提升,他们就会这样做.他们使用0-based堆应该告诉你,基于1的堆的任何性能增益都是虚幻的.

有关更完整的讨论,请参见http://blog.mischel.com/2016/09/19/but-thats-the-way-weve-always-done-it/.