我在数组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的数组），但他们没有大脑去改变子代和父代的计算，所以我们最终在这种特殊情况下，要容纳100个物料，您必须分配101个物料：
int a[101];
当有人打电话给那个不一致的人时，他想出了一个似是而非的性能争论。
是的，代码中有一条额外的增量指令用于计算左子索引，而在计算孩子的父索引时有一条额外的递减指令。在二进制堆所做的更广泛的上下文中，这两条指令不会对使用该堆的任何程序的运行时间产生实际影响。没有。如果差异是可以测量的，那肯定是嘈杂的。您的计算机上发生了许多其他事情，它们会对程序的性能产生更大的影响。
如果要编写需要高性能优先级队列的程序，那么首先要对二进制堆做什么呢？如果您真的要在优先级队列中存储大量内容，则可能应该使用“配对”堆之类的东西，尽管内存成本更高，但它的性能要优于二进制堆。
C ++ STL
priority_queue，Java PriorityQueue和python的heapq都使用基于0的二进制堆。编写这些程序包的人都了解性能注意事项。如果使用基于1的二进制堆可以显着提高性能，那么他们会这样做。它们与基于0的堆一起使用应该告诉您，基于1的堆获得的任何性能提升都是虚幻的。有关更完整的讨论，请参见http://blog.mischel.com/2016/09/19/but-thats-the-way-weve-always-done-it/。