php - PHP SplHeap 真的是堆吗？

Question

Heap 的 PHP 实现真的是完整的实现吗？

当我读到这篇文章时，http://en.wikipedia.org/wiki/Heap_%28data_structure%29 ，我认为子节点有特定的父节点，而父节点有特定的子节点。

然而，当我查看 PHP 文档中的示例时，http://au.php.net/manual/en/class.splheap.php , 看起来子节点都共享相同的'级别'，但具体的父/子信息并不重要。

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

在我的应用程序中，当用户选择“节点 156”时，我需要知道它的 child 是谁，以便我可以对他们进行访问。 (我可以让他们的身份为“节点 1561”、“节点 1562”等，所以关系很明显)。

PHP Heap实现不完整？我应该忘记 Spl 类并走我自己的路吗？或者我错过了堆应该如何运作的一些东西？或者我应该查看特定的堆变体？

非常感谢!

Answer 1

此堆实现的 API 不允许数组访问，而这正是您在本例中所需要的。堆通常用于实现其他结构，使您可以轻松地从顶部删除项目。

您可以创建一个包装器迭代器来寻找您需要的位置。我怀疑这将是一个性能不佳的解决方案，而不是一个很好的解决方案。

---

在这种情况下，我认为您需要的是 BinaryTree。在树上给定一个位置，你可以从它的 child 那里下去，因为它们是直接相连的。我有一个BinarySearchTree这将使树保持有序，您可以调用 getRoot 来获取 BinaryTree 的副本。还有一个 AvlTree这将使树保持平衡以进行最佳搜索。