Ich finde widersprüchliche Informationen über die Suche auf einem binären Heap. Danach https://en.wikipedia.org/wiki/Binary_heap, es ist O (n) (edit: es ist eigentlich O (log n)), nach diesem Search an element in a heap, es ist O (n/2).Komplexität der Binärbaumsuche
Wikipedia war einfach falsch. Binäre Heaps sind nicht darauf ausgelegt, nach einzelnen Elementen durchsucht zu werden, sondern sind nur für den Zugriff auf das kleinste Element optimiert. So können sie beispielsweise in der Zeit Θ (n) konstruiert werden; Die Reihenfolge, die sie benötigen, ist nicht annähernd so streng wie bei einem binären Suchbaum.
Es sieht aus wie jemand Wikipedia aktualisiert hat, was gut ist. Danke, dass du das unterstrichen hast!
Eine Anmerkung - die Terminologie O (n/2) gilt, obwohl technisch korrekt, als eine schlechte Verwendung der Groß-O-Notation. Die Big-O-Notation ignoriert konstante Faktoren, daher ist O (n/2) dasselbe wie O (n). Wenn Sie die bestimmte Anzahl von Operationen zählen möchten, die Sie am Ende ausführen, vermeiden Sie die Groß-O-Notation und sagen Sie etwas wie "genau n/2 Vergleiche sind erforderlich".
Es tut mir leid, ich meinte, dass der Wikipedia-Link sagt, es ist O (log n). –
Ein echter binärer Haufen wäre O (n/2) wegen der in Wikipedia erwähnten * Heap-Eigenschaft *: Wenn A ein Elternknoten von B ist, dann ist der Schlüssel von Knoten A in Bezug auf den Schlüssel von Knoten B mit geordnet die gleiche Reihenfolge gilt für den ganzen Haufen. * Die Reihenfolge teilt im Wesentlichen den Aufwand der Suche in zwei Hälften. Diese Komplexität ist jedoch in einem Graphen linear, so dass es im Wesentlichen nach O (n) gemittelt wird. Der binäre Suchbaum hat Kinder angeordnet und ermöglicht eine echte binäre Suche mit einer Komplexität von O (log n). –
Wenn "Suchen" bedeutet, den Heap nach einem bestimmten Datum zu durchsuchen, sollte es "O (n)" sein. Ich bin mir nicht sicher, was die Wiki-Seite eigentlich bedeutet. Aber in der Regel unterstützen Heaps die "Such" -Operation nicht - sie sind einfach nicht dazu gedacht. Vielleicht sollte jemand die Wiki-Seite modifizieren oder deutlicher benennen. – WhatsUp