根位于 arr[0] 的二进制堆有什么好处
What are the benefits of a binary heap with root at arr[0]
我正在数组 arr 上写二进制堆。
除叶节点外的每个节点都有两个子节点。
根可以在 arr[0] 或 arr[1]。
Why in a heap implemented by array the index 0 is left unused? 接受的答案说 arr[1] 更快。
但是该答案下面的一条评论说大多数实现都将 root 置于 arr[0]。
将根置于 arr[0] 有什么好处？
我就是回答您所链接问题的人。
使用具有从 0 开始的数组的语言创建一个根位于 arr[1] 的二进制堆是愚蠢的。不是因为它浪费了微不足道的 space，而是因为它创建了不必要的混乱代码而没有任何好处。
为什么代码很混乱？因为它打破了我们作为程序员多年来一直遵循的基本规则：数组从 0 开始。如果你想要一个包含 100 个项目的数组，你可以这样声明它：
int a[100];
二进制堆除外。因为一些白痴在 1973 年将原始二进制堆代码从 Algol（其数组从 1 开始）转换为 C（从 0 开始的数组）没有大脑改变子和父计算，我们最终在这种特殊情况下，您必须分配 101 件物品来存放 100 件物品：
int a[101];
当有人就此不一致问题打电话给那个人时，他想出了一个似是而非的性能参数。
是的，在计算左子索引的代码中有一个额外的自增指令，在计算子父索引时有一个额外的自减指令。在二进制堆的更广泛上下文中，这两条指令对使用该堆的任何程序的 运行 时间没有实际影响。 None。如果差异甚至可以测量，那肯定会很吵。您的计算机上发生的许多其他事情会对您的程序性能产生更大的影响。
如果您正在编写一个需要高性能优先级队列的程序，那么您首先要用二叉堆做什么？如果你真的要在你的优先级队列中存储大量的东西，你可能应该使用像配对堆这样的东西，它会优于二进制堆，尽管内存成本更高。
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/。
我正在数组 arr 上写二进制堆。
除叶节点外的每个节点都有两个子节点。
根可以在 arr[0] 或 arr[1]。
Why in a heap implemented by array the index 0 is left unused? 接受的答案说 arr[1] 更快。
但是该答案下面的一条评论说大多数实现都将 root 置于 arr[0]。
将根置于 arr[0] 有什么好处？
我就是回答您所链接问题的人。
使用具有从 0 开始的数组的语言创建一个根位于 arr[1] 的二进制堆是愚蠢的。不是因为它浪费了微不足道的 space，而是因为它创建了不必要的混乱代码而没有任何好处。
为什么代码很混乱？因为它打破了我们作为程序员多年来一直遵循的基本规则：数组从 0 开始。如果你想要一个包含 100 个项目的数组，你可以这样声明它：
int a[100];
二进制堆除外。因为一些白痴在 1973 年将原始二进制堆代码从 Algol（其数组从 1 开始）转换为 C（从 0 开始的数组）没有大脑改变子和父计算，我们最终在这种特殊情况下，您必须分配 101 件物品来存放 100 件物品：
int a[101];
当有人就此不一致问题打电话给那个人时，他想出了一个似是而非的性能参数。
是的，在计算左子索引的代码中有一个额外的自增指令，在计算子父索引时有一个额外的自减指令。在二进制堆的更广泛上下文中，这两条指令对使用该堆的任何程序的 运行 时间没有实际影响。 None。如果差异甚至可以测量，那肯定会很吵。您的计算机上发生的许多其他事情会对您的程序性能产生更大的影响。
如果您正在编写一个需要高性能优先级队列的程序，那么您首先要用二叉堆做什么？如果你真的要在你的优先级队列中存储大量的东西，你可能应该使用像配对堆这样的东西，它会优于二进制堆，尽管内存成本更高。
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/。