根在arr[0]的二进制堆有什么好处

Question

我正在一个数组< code>arr上写一个二进制堆。

除了叶节点，每个节点都有两个子节点。

根可以位于 arr[0] 或 arr[1]。

公认的答案是为什么在数组实现的堆中索引0未使用？说arr[1]更快。

但是答案下面的一条评论说大多数实现都将root放在arr[0]。

将根放在 arr[0] 有什么好处？

Answer 1

我是回答您链接的问题的人。

在一种具有基于0的数组的语言中创建一个根在< code>arr[1]的二进制堆是愚蠢的。不是因为它浪费了微不足道的空间，而是因为它创建了毫无益处的不必要的混乱代码。

为什么代码令人困惑？因为它打破了我们作为程序员多年来一直遵循的基本规则：数组从0开始。如果你想要一个包含100个项目的数组，你可以这样声明：

int a[100];

除了二进制堆。因为一些在1973年将原始二进制堆代码从Algol(其数组是基于1的)转换为C(基于0的数组)的白痴没有改变子和父计算的头脑，我们已经结束了这个特例，在这里保存100个项目，您必须分配101:

int a[101];

当有人打电话给那个人关于不一致时，他想出了一个似是而非的表演论点。

是的，代码中有一个额外的增量指令用于计算左子索引，当计算孩子的父索引时，有一个额外的减量指令。在二进制堆所做的更广泛的上下文中，这两条指令对任何使用堆的程序的运行时间都没有实际影响。没有。如果差异甚至是可测量的，它肯定会很吵。您的计算机上发生了许多其他事情，这些事情会对您的程序性能产生更大的影响。

如果你正在编写一个需要高性能优先级队列的程序，你首先用二进制堆做什么？如果你真的要在优先级队列中存储大量的东西，你可能应该使用像配对堆这样的东西，它将优于二进制堆，尽管内存成本更高。

C STL＜code＞priority_queue＜/code＞、Java＜code＞PriorityQueue＜/code>和python的heapq都使用基于0的二进制堆。编写这些包的人了解性能考虑因素。如果使用基于1的二进制堆可以显著提高性能，那么他们会这样做。他们使用基于0的堆应该告诉你，从基于1的堆中获得的任何性能都是虚幻的。

请参阅 http://blog.mischel.com/2016/09/19/but - 这就是我们总是做的方式 - 对于更完整的讨论。