Ich erinnerte mich, dass Heap kann verwendet werden, um zu suchen, ob ein Element ist es oder nicht mit O (logN) Zeit Komplexität. Aber plötzlich verstehe ich die Details nicht. Ich kann nur finden, Getmin löschen hinzufügen und so weiter.Suche ein Element in einem Haufen
Kann jemand einen Hinweis geben?
Sie müssen jedes Element im Heap durchsuchen, um festzustellen, ob ein Element darin enthalten ist.
Eine Optimierung ist jedoch möglich (wir nehmen hier einen Max-Heap an). Wenn Sie einen Knoten mit einem niedrigeren Wert als das gesuchte Element erreicht haben, müssen Sie nicht weiter von diesem Knoten aus suchen. Aber selbst mit dieser Optimierung ist die Suche immer noch O (N) (im Durchschnitt müssen N/2 Knoten überprüft werden).
Ich denke, was Sie suchen, ist ein BST (binary search tree).
Nicht hilfreich, wenn Sie bereits eine Prioritätswarteschlange haben und prüfen möchten, ob sie ein bestimmtes Element enthält. – finnw
Ist das völlig richtig? Nehmen Sie den folgenden Heap als Beispiel: '[5, 4, 1, 3]' Wenn ich diesen Heap (in Form eines Arrays) für die Zahl 3 suche, drücke ich 1 und höre hier laut Ihrem Algorithmus auf Schluss es ist nicht auf dem Haufen, wenn es tatsächlich ist? Fehle ich hier etwas? –
Mit der Optimierung wird der Teilbaum mit Wurzel 1 nicht weiter durchsucht, da er nicht 3 enthalten kann. 3 ist in einem anderen Teilbaum. Ich stimme zu, dass eine lineare Suche (im Gegensatz zu einer rekursiven) eine falsche Antwort geben kann. –
@JamesSanders Es gilt in allen Fällen, sogar für eine lineare Suche. Der vollständige Binärbaum hat den Wert 3 als linkes Kind von 4, und 1 wird auf der gleichen Höhe wie 4 sein. Auch wenn Sie eine lineare Suche durchführen, sagt die Optimierung, dass 4> 3, also müssen Sie mindestens , vergleichen Sie die Kinder von 4, zusätzlich zu allen anderen Elementen in der gleichen Höhe wie 4. – lee