Gibt es eine Möglichkeit, PHPs SplHeap neu berechnen zu lassen? (aka: Add-Heap zu SplHeap?)

Ich verwende ein SplHeap , um Diagrammknoten eines Baumes mit gerichteten Kanten zu halten, die von den Blättern zum Stamm durchlaufen werden . Dazu berechne ich die "fan-in" von Knoten voraus und lege sie in den Heap, so dass ich immer den Knoten mit dem kleinsten Fan-In (0) daraus finden kann.

Nach dem Besuch eines Knotens reduziere ich das Fan-In seines Nachfolgers um 1. Dann muss natürlich der Heap neu berechnet werden, weil der Nachfolger dort an der falschen Stelle ist. Ich habe versucht recoverFromCorruption() , aber es tut nichts und hält den Haufen in der falschen Reihenfolge (Knoten mit größeren fanIn bleibt vor kleineren fanIn ).

Als Workaround erstelle ich jetzt nach jedem Besuch einen neuen Heap, der jedesmal eine vollständige O (N * log (N)) Sortierung ergibt.

Es sollte jedoch möglich sein, Heap-Operationen für den geänderten Heap-Eintrag durchzuführen, bis er sich in O (log (N)) an der richtigen Position befindet.

Die API für SplHeap erwähnt keinen Up-Heap (oder das Löschen eines beliebigen Elements - es könnte dann wieder hinzugefügt werden). Kann ich irgendwie eine Klasse von SplHeap ableiten oder muss ich einen reinen PHP-Heap von Grund auf neu erstellen?

BEARBEITEN : Codebeispiel:

Vollständiger Code auch verfügbar: Ссылка

BEARBEITEN 2 :

Dies bedeutet, dass Benutzer 1 und Benutzer 3 für Benutzer 2 und Benutzer 2 für die Abstimmung stimmen Benutzer 4 , übergibt 3 Stimmen (2 erhalten + eigene). Das nennt man delegatives Voting: Mein Algorithmus gibt die Stimmen "von unten" (die Blätter) weiter, wo ich bereits weiß, wie viel Gewicht (Verantwortung / Repräsentation / wie es dir gefällt ...) jeder Nutzer hat.