Binäre Heaps und binäre Suchbäume in Algorithmen - Dummies

Eine spezielle Art von Baumstruktur ist der Binär-Heap, der jedes der Knotenelemente in einer speziellen Reihenfolge platziert. Suchbäume ermöglichen es Ihnen, schnell nach Daten zu suchen. Datenelemente zu erhalten, sie in einer sortierten Reihenfolge in einem Baum zu platzieren und dann diesen Baum zu durchsuchen, ist eine der schnelleren Möglichkeiten, Informationen zu finden.

In einem binären Heap enthält der Wurzelknoten immer den kleinsten Wert. Wenn Sie die Zweige betrachten, sehen Sie, dass Zweige auf höherer Ebene immer einen kleineren Wert haben als Zweige und Blätter auf niedrigeren Ebenen. Der Effekt besteht darin, den Baum ausgeglichen und in einer vorhersagbaren Reihenfolge zu halten, so dass das Suchen äußerst effizient wird. Die Kosten sind, den Baum ausgeglichen zu halten.

Von allen Aufgaben, die Anwendungen erledigen, ist das Suchen zeitaufwendiger und auch das am meisten benötigte. Auch wenn das Hinzufügen von Daten (und das spätere Sortieren) einige Zeit in Anspruch nimmt, kommt der Nutzen für die Erstellung und Pflege eines Datasets aus der Verwendung nützlicher Arbeit, dh der Suche nach wichtigen Informationen. Folglich können Sie manchmal mit einer weniger effizienten CRUD-Funktionalität und sogar einer weniger als optimalen Sortierroutine auskommen, aber Suchvorgänge müssen so effizient wie möglich ablaufen. Das einzige Problem ist, dass keine Suche jede Aufgabe mit absoluter Effizienz durchführt. Sie müssen also Ihre Optionen auf der Grundlage Ihrer Erwartungen an die Suchroutinen abwägen.

Zwei der effizienteren Suchmethoden beinhalten die Verwendung des binären Suchbaums (BST) und des binären Heaps. Beide Suchverfahren beruhen auf einer baumartigen Struktur, um die Schlüssel zu halten, die zum Zugriff auf Datenelemente verwendet werden. Die Anordnung der beiden Methoden ist jedoch unterschiedlich, weshalb man beim Durchführen bestimmter Aufgaben Vorteile gegenüber dem anderen hat. Diese Abbildung zeigt die Anordnung für eine BST.

Die Anordnung der Tasten bei Verwendung eines BST.

Beachten Sie, dass die Tasten einer Reihenfolge folgen, in der links kleinere Zahlen und rechts größere Zahlen angezeigt werden. Der Wurzelknoten enthält einen Wert, der sich in der Mitte des Tastenbereichs befindet und dem BST einen leicht verständlichen, ausgewogenen Ansatz zum Speichern der Schlüssel gibt. Vergleichen Sie diese Anordnung mit dem hier gezeigten Binärhaufen.

Die Anordnung der Schlüssel bei Verwendung eines binären Heaps.

Jede Ebene enthält Werte, die kleiner als die vorherige Ebene sind, und die Wurzel enthält den maximalen Schlüsselwert für die Struktur. Zusätzlich erscheinen in diesem speziellen Fall die kleineren Werte auf der linken Seite und die größeren auf der rechten Seite (obwohl diese Reihenfolge nicht strikt durchgesetzt wird). Die Abbildung zeigt tatsächlich einen binären Max-Heap von. Sie können auch einen Binär-Min-Heap erstellen, in dem der Stamm den niedrigsten Schlüsselwert enthält und jede Ebene zu höheren Werten aufgebaut wird, wobei die höchsten Werte als Teil der Blätter erscheinen.

Wie bereits erwähnt, hat BST einige Vorteile gegenüber Binär-Heap, wenn es verwendet wird, um eine Suche durchzuführen. Die folgende Liste bietet einige der Highlights dieser Vorteile:

• Die Suche nach einem Element erfordert O (log n) Zeit, im Gegensatz zu O (n) Zeit für einen binären Heap.
• Das Drucken der Elemente in Reihenfolge erfordert nur O (log n) Zeit, im Gegensatz zu O (n log n) Zeit für einen binären Heap.
• Das Finden des Bodens und der Decke erfordert O (log n) Zeit.
• Das Finden von Kth kleinstem / größtem Element erfordert O (log n) Zeit, wenn der Baum richtig konfiguriert ist.

Ob diese Zeiten wichtig sind, hängt von Ihrer Anwendung ab. BST funktioniert am besten in Situationen, in denen Sie mehr Zeit mit der Suche verbringen und weniger Zeit mit dem Aufbau des Baums verbringen. Ein binärer Heap funktioniert am besten in dynamischen Situationen, in denen sich die Schlüssel regelmäßig ändern. Der Binär-Heapspeicher bietet auch Vorteile, wie in der folgenden Liste beschrieben:

• Das Erstellen der erforderlichen Strukturen erfordert weniger Ressourcen, da Binär-Heapspeicher auf Arrays basieren und diese auch besser cache-fähig sind.
• Die Erstellung eines binären Heapspeichers erfordert eine O (n) -Zeit im Gegensatz zu BST, für die O (n log n) erforderlich ist.
• Die Verwendung von Zeigern zur Implementierung des Baums ist nicht erforderlich.
• Wenn Sie sich auf binäre Heap-Variationen stützen (z. B. der Fibonacci-Heap), bietet dies Vorteile wie das Erhöhen und Verringern von Schlüsselzeiten von O (1) Zeit.