一个 PHP SplHeap 真的是一个堆吗？

Question

PHP实现的堆是否是一个完整的实现？

当我阅读这篇文章http://en.wikipedia.org/wiki/Heap_%28data_structure%29时，我得到的想法是子节点有一个特定的父节点，并且父节点有特定的子节点。

然而当我查看PHP文档中的例子http://au.php.net/manual/en/class.splheap.php时，似乎所有的子节点都共享同一个“级别”，但具体的父/子信息并不重要。

例如，在PHP示例中排名第10的三个节点中，哪个节点是每个节点的父节点？

在我的应用程序中，当用户选择“节点156”时，我需要知道它的子节点是谁，以便我可以访问它们每一个（我可以将它们的身份设置为“节点1561”，“节点1562”等，以便关系明显）。

PHP堆实现是否不完整？我应该忘记Spl类，走自己的路吗？或者我对堆的操作方式有所遗漏？或许我应该看一下特定的堆变体？

非常感谢！

- DatsunBing

---

我在谷歌上找到了这个开源项目。实际上，它并不是你要找的东西，但你可以尝试使用这个脚本来进行测试，自己获取结果。 - Leri

Answer 1

这个堆实现的API不允许数组访问，在这种情况下你需要它。通常使用堆来实现其他结构，可以轻松地从顶部删除项目。

您可以创建一个包装迭代器，以查找所需的位置。我怀疑这将是一个性能不佳且不太好的解决方案。

---

在这种情况下，我认为你需要一个二叉树。给定树中的一个位置，你可以沿着它的子节点往下遍历，因为它们直接相连。我有一个BinarySearchTree，可以保持树的有序，并且你可以调用getRoot来获取BinaryTree的副本。还有一个AvlTree，可以保持树的平衡以获得最佳搜索效果。

- Levi Morrison

Answer 2

堆通常用于回答“集合中最大/最小元素是什么”的问题。

虽然堆可以偶然高效地回答“最大/最小节点的子节点是谁”，但当需要访问任意节点来回答问题时（即不是最大节点的节点），堆并不是一个好的数据结构。如果需要表示和维护特定的父子关系，也不应使用堆，因为子节点会在不同的父节点之间交换。

因此，对于这些情况，PHP的堆实现显然不是不完整的。您只需要使用不同的数据结构即可。

- goat