Ist ein PHP SplHeap wirklich ein Heap?

Question

Ist die PHP-Implementierung eines Heap wirklich eine vollständige Implementierung?

Wenn ich diesen Artikel, http://en.wikipedia.org/wiki/Heap_%28data_structure%29, lesen, bekomme ich die Idee, dass ein Kind Knoten einen bestimmten Elternteil hat, und dass ein Elternteil bestimmte Kinder hat.

Wenn ich mir das Beispiel in der PHP-Dokumentation, http://au.php.net/manual/en/class.splheap.php, ansehe, scheint es, dass Kindknoten alle die gleiche 'Ebene' teilen, aber die spezifischen Eltern/Kind-Informationen sind nicht wichtig.

Zum Beispiel, welcher Knoten ist der Elternteil für jeden der drei Knoten, die im PHP-Beispiel auf Platz 10 stehen?

In meiner Anwendung, wenn ein Benutzer wählt "Knoten 156", muss ich wissen, wer seine Kinder sind, so dass ich ihnen jeweils einen Besuch bezahlen kann. (Ich könnte ihre Identitäten 'Knoten 1561', 'Knoten 1562' usw. machen, also ist die Beziehung offensichtlich).

Ist die PHP-Heap-Implementierung unvollständig? Soll ich die Spl-Klasse vergessen und meinen eigenen Weg gehen? Oder fehlt mir etwas davon, wie Heaps funktionieren sollten? Oder sollte ich vielleicht eine bestimmte Heap-Variante betrachten?

Vielen Dank!

Answer 1

Ein Heap wird normalerweise verwendet, um Fragen zu beantworten, die sich um "was ist das max/min-Element in der Menge" drehen.

Während ein Heap zufällig zufällig "wer sind die Kinder des Max/Min-Knotens" beantworten kann, hebt sich ein Heap nicht als gute Datenstruktur hervor, wenn Sie auf einen beliebigen Knoten zugreifen müssen, um Ihre Frage zu beantworten (ein Knoten, der nicht der maximale Knoten ist). Es ist auch nicht die zu verwendende Datenstruktur, wenn bestimmte übergeordnete untergeordnete Beziehungen dargestellt und gepflegt werden müssen, da die untergeordneten Elemente zwischen verschiedenen übergeordneten Knoten ausgetauscht werden können.

So PHP-Heap-Implementierung ist definitiv nicht unvollständig aus diesen Gründen. Sie brauchen einfach eine andere Datenstruktur.

Answer 2

Die API für diese Heap-Implementierung erlaubt keinen Array-Zugriff, was Sie in diesem Fall benötigen. Heaps werden normalerweise verwendet, um andere Strukturen zu implementieren, mit denen Sie Objekte einfach von oben entfernen können.

Sie könnten einen Wrapper-Iterator erstellen, der nach den Positionen sucht, die Sie benötigen. Ich vermute, dass dies eine schlecht funktionierende und keine sehr gute Lösung wäre.

---

In dieser Situation ist ein BinaryTree, was ich denke, dass Sie brauchen. Wenn du einen Platz im Baum hast, kannst du die Kinder untergehen, weil sie direkt miteinander verbunden sind. Ich habe eine BinarySearchTree, die den Baum bestellt und Sie können getRoot anrufen, um eine Kopie der BinaryTree zu bekommen. Es gibt auch einen AvlTree, der den Baum für eine optimale Suche im Gleichgewicht hält.