我正在数组上写一个二进制堆arr.
除叶节点外，每个节点都有两个子节点。
根可以位于arr[0] or arr[1].
接受的答案在为什么在数组实现的堆中索引 0 未被使用？ https://stackoverflow.com/questions/22900388/why-in-a-heap-implemented-by-array-the-index-0-is-left-unused says arr[1]是比较快的。
但该答案下面的一条评论说，大多数实施都扎根于arr[0].
扎根有什么好处arr[0]?
我是回答您链接的问题的人。
创建根位于的二进制堆arr[1]在具有从 0 开始的数组的语言中这是愚蠢的。不是因为它浪费了一点点空间，而是因为它创建了不必要的混乱代码，却没有任何好处。
为什么代码很混乱？因为它打破了我们作为程序员多年来一直遵循的基本规则：数组从 0 开始。如果您想要一个包含 100 个项目的数组，您可以这样声明：
int a[100];
除了二进制堆。因为一些白痴在 1973 年将原始二进制堆代码从 Algol（其数组从 1 开始）转换为 C（从 0 开始数组），但没有头脑来更改子级和父级计算，所以我们最终得到了结果在这种特殊情况下，要保存 100 个项目，您必须分配 101 个：
int a[101];
当有人就这种不一致问题给那个人打电话时，他提出了一个似是而非的绩效论点。
是的，代码中有一个额外的递增指令用于计算左子索引，并且在计算子父索引时有一个额外的递减指令。在二进制堆的更广泛的上下文中，这两条指令对使用该堆的任何程序的运行时间没有实际影响。没有任何。如果差异甚至是可测量的，那么它肯定会很吵。您的计算机上发生的许多其他事情将对您的程序性能产生更大的影响。
如果您正在编写一个需要高性能优先级队列的程序，那么您首先要使用二进制堆做什么？如果你真的要在优先级队列中存储大量的东西，你可能应该使用像配对堆这样的东西，它的性能优于二进制堆，尽管内存成本更高。
C++ STLpriority_queue, 爪哇PriorityQueue，以及python的heapq都使用从0开始的二进制堆。编写这些包的人了解性能考虑因素。如果使用基于 1 的二进制堆能够显着提高性能，他们就会这样做。他们使用基于 0 的堆应该告诉您，从基于 1 的堆获得的任何性能提升都是虚幻的。
请参阅我的博客文章但这就是我们一直以来的做法！ https://blog.mischel.com/2023/01/19/but-thats-the-way-weve-always-done-it/进行更完整的讨论。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
