Prims Algorithmus mit Treaps

Question

kann der Algorithmus von PRIM von Treaps implementiert werden, um die Ausführung zu beschleunigen, da ein normaler Heap ein Problem darstellt, um den Schlüsselwert zu aktualisieren, während Sie die Scheitelpunkte in Haufen aufbewahren, die andernfalls o (v) zum Speichern des Standorts von Scheitelpunkten in Heap

Answer 1

Dies wird nicht notwendigerweise den Algorithmus von Prim beliebig schneller machen.Betrachten Sie den folgenden degenerierten Fall - Sie haben N-Knoten V1, V2, ..., VN, und ihre Prioritäten sind so, dass p (v1)

Entschuldigung für das negative Ergebnis, aber ich hoffe das hilft das!