Python 中最大堆的基于树节点的实现（不是动态数组）
Tree-node based implementation (not dynamic array) of max heap in Python
我看过一些关于 implementation of a max-heap in python based on dynamic arrays 和索引的资源。但是，我还没有看到基于 OOP 树节点的实现。我想知道这是否有原因；基于节点的实现会更糟 time/space 复杂性吗？这个数组实现是否更加简洁以至于树节点实现不值得付出努力？其他原因？
原因就是你列出的那些。基于 tree-node 的算法在 space 和时间上的效率都较低。
Space：数组实现只需要存储数据负载，概念树关系是使用简单的算术运算确定的。 tree-node 实施需要为父级、left-child 和 right-child 额外存储。赢去阵。
时间：一个好的堆实现通过 complete binary tree 获得效率。保持完整性对于数组实现来说是微不足道的。让我们专注于将新值推入现有树。当您将数据推送到包含 n 值的 zero-based 数组时，它最初将在概念上放置在数组的 n 位置，然后根据需要向上冒泡。冒泡过程在概念上涉及向下滑动连续的父值，直到不再违反堆 属性，然后在该位置插入新值。这受 log(n) 的限制，因为树是完整的，但通常可以更快地终止。相比之下，node-based 树的完整性具有挑战性。首先需要确定将成为新节点父节点的节点，这需要遍历树 or 维护每个节点的邻居引用 or 维护一个指向第 nth 位置的父项的指针。更新一系列推送和弹出的指针涉及额外的工作，如果你搞砸了，上帝会帮助你。冒泡过程必须对所有遍历的节点、它们的父节点和它们的兄弟节点进行左、右和父节点的指针更新。再一次，胜利属于数组实现。
回收数组位置很容易——只需将新数据放在下一个位置进行推送并增加计数（如果需要，让 python 扩展数组），然后减少计数但保留后备数组 as-is 用于持久性有机污染物。对于 node-based 树，您要么需要不断地成为 allocating/freeing 个节点（计算量大），要么将以前使用过的节点存储在辅助容器中，例如要回收的堆栈（额外存储）。
底线：基于节点的实现是可能的，但不值得。
我看过一些关于 implementation of a max-heap in python based on dynamic arrays 和索引的资源。但是，我还没有看到基于 OOP 树节点的实现。我想知道这是否有原因；基于节点的实现会更糟 time/space 复杂性吗？这个数组实现是否更加简洁以至于树节点实现不值得付出努力？其他原因？
原因就是你列出的那些。基于 tree-node 的算法在 space 和时间上的效率都较低。
Space：数组实现只需要存储数据负载，概念树关系是使用简单的算术运算确定的。 tree-node 实施需要为父级、left-child 和 right-child 额外存储。赢去阵。
时间：一个好的堆实现通过 complete binary tree 获得效率。保持完整性对于数组实现来说是微不足道的。让我们专注于将新值推入现有树。当您将数据推送到包含 n 值的 zero-based 数组时，它最初将在概念上放置在数组的 n 位置，然后根据需要向上冒泡。冒泡过程在概念上涉及向下滑动连续的父值，直到不再违反堆 属性，然后在该位置插入新值。这受 log(n) 的限制，因为树是完整的，但通常可以更快地终止。相比之下，node-based 树的完整性具有挑战性。首先需要确定将成为新节点父节点的节点，这需要遍历树 or 维护每个节点的邻居引用 or 维护一个指向第 nth 位置的父项的指针。更新一系列推送和弹出的指针涉及额外的工作，如果你搞砸了，上帝会帮助你。冒泡过程必须对所有遍历的节点、它们的父节点和它们的兄弟节点进行左、右和父节点的指针更新。再一次，胜利属于数组实现。
回收数组位置很容易——只需将新数据放在下一个位置进行推送并增加计数（如果需要，让 python 扩展数组），然后减少计数但保留后备数组 as-is 用于持久性有机污染物。对于 node-based 树，您要么需要不断地成为 allocating/freeing 个节点（计算量大），要么将以前使用过的节点存储在辅助容器中，例如要回收的堆栈（额外存储）。
底线：基于节点的实现是可能的，但不值得。