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」時，我需要知道他的孩子是誰，以便我可以每次都拜訪他們。 （我可以讓他們的身份「節點1561」，「節點1562」等，所以關係很明顯）。

PHP堆實現是否不完整？我應該忘記Spl課程並以我自己的方式走？或者我錯過了堆應該如何運作？或者，也許我應該看一個特定的堆變體？

謝謝堆！

Answer 1

堆通常用於回答圍繞「集合中最大/最小元素是什麼」的問題。

雖然堆可能巧合地高效地回答「誰是最大/最小節點的孩子」，但是當您需要訪問任意節點來回答您的問題時，堆並不是一個很好的數據結構（不是最大節點的節點）。如果存在需要表示和維護的特定父子關係，那麼也不是數據結構，因爲子項可以在不同的父節點之間進行交換。

所以php的堆實現絕對不是不完整的這些理由。你只需要一個不同的數據結構。

Answer 2

此堆實現的API不允許數組訪問，這是您在這種情況下需要的。堆通常用於實現其他結構，使您可以輕鬆地從頂部移除項目。

你可以創建一個包裝器迭代器，尋找你需要的位置。我懷疑這將是一個表現不佳的解決方案，而不是一個很好的解決方案。

---

在這種情況下，我認爲你需要一個BinaryTree。鑑於樹中的一個位置，你可以放下它的孩子，因爲它們直接相連。我確實有一個BinarySearchTree，這將保持訂購的樹，你可以撥打getRoot獲得BinaryTree的副本。還有一個AvlTree這將保持樹最佳搜索平衡。