Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Haufen

Heap und Prioritätswarteschlange:

Die Prioritätswarteschlange ist ein abstrakter Datentyp und der Heap ist eine Datenstruktur. Der Heap ist also keine Prioritätswarteschlange. Der Heap ist eine Möglichkeit, eine Prioritätswarteschlange zu implementieren.
Es gibt viele Möglichkeiten, Prioritätswarteschlangen zu implementieren, z. B. Arrays und verknüpfte Listen. Diese Implementierungen können jedoch nur garantieren, dass einer der Einfüge- und Löschvorgänge in der Zeitkomplexität O(1)O(1) abgeschlossen werden kann, während der andere Vorgang in O(N)O(N) abgeschlossen werden muss Zeitkomplexität. Der Heap kann ermöglichen, dass der Einfügungsvorgang der Prioritätswarteschlange innerhalb der Zeitkomplexität von O(log N)O(logN) und der Löschvorgang innerhalb der Zeitkomplexität von O(log N)O(logN) abgeschlossen werden. .

Ein Heap ist ein spezieller Binärbaum, der die folgenden Bedingungen erfüllt:

1. Vollständiger Binärbaum (Knoten werden in der Reihenfolge von links nach rechts platziert);
2. Der Wert jedes Knotens muss größer oder gleich oder kleiner oder gleich dem Wert seines untergeordneten Knotens sein.

Merkmale des Heaps:

1. Elemente können mit einer Zeitkomplexität von O(logN) in den Heap eingefügt werden;
2. Elemente können mit einer Zeitkomplexität von O(logN) aus dem Heap gelöscht werden;
3. Der maximale oder minimale Wert im Heap kann innerhalb der Zeitkomplexität O(1) ermittelt werden.

Heap-Klassifizierung:

Max. Heap: Der Wert jedes Knotens im Heap ist größer oder gleich dem Wert seines untergeordneten Knotens. Das oberste Element (Wurzelknoten) des Max-Heaps ist der Maximalwert im Heap.
Minimaler Heap: Der Wert jedes Knotens im Heap ist kleiner oder gleich dem Wert seines untergeordneten Knotens. Das oberste Element (Wurzelknoten) eines Min-Heaps ist der Mindestwert im Heap.
Die aktuelle Knotennummer ist i, die Nummer des linken Kindes ist 2i und die Nummer des rechten Kindes ist 2i+1.

Zeitkomplexität und Raumkomplexität

Heap-Sortierung

Theorie: Heap-Sortierung bezieht sich auf die Verwendung der Datenstruktur des Heaps, um einen Satz ungeordneter Elemente zu sortieren.

Die Schritte des Min-Heap-Sortieralgorithmus sind wie folgt:

Heften Sie alle Elemente in einen minimalen Heap;
Nehmen Sie das oberste Element des Heaps heraus, löschen Sie es und platzieren Sie das oberste Element des Heaps im Datensatz T, in dem geordnete Elemente gespeichert sind.
Zu diesem Zeitpunkt wird der Heap an den neuen Mindestheap angepasst.
Wiederholen Sie die Schritte 3 und 4, bis der Heap keine Elemente mehr enthält.
An diesem Punkt wird ein neuer Datensatz T erhalten, in dem die Elemente in der Reihenfolge von klein nach groß angeordnet sind.

Die Schritte des Max-Heap-Sortieralgorithmus sind wie folgt:

Heften Sie alle Elemente in einen maximalen Heap.
Nehmen Sie das oberste Element des Heaps heraus, löschen Sie es und platzieren Sie das oberste Element des Heaps im Datensatz T, in dem geordnete Elemente gespeichert sind.
Zu diesem Zeitpunkt wird der Heap an den neuen maximalen Heap angepasst.
Wiederholen Sie die Schritte 3 und 4, bis der Heap keine Elemente mehr enthält.
An diesem Punkt wird ein neuer Datensatz T erhalten, in dem die Elemente in der Reihenfolge von groß nach klein angeordnet sind.
Zeitkomplexität: O(Nlog N). N ist die Anzahl der Elemente im Heap.

Raumkomplexität: O(N). N ist die Anzahl der Elemente im Heap.