Was für eine Art ist die Heap-Sortierung?

Heap-Sortierung ist eine Methode zum Generieren eines maximalen Heaps aus einer ungeordneten Reihenfolge, wobei die Positionen des obersten Elements des Heaps mit dem letzten Element ausgetauscht werden und ein maximaler Heap mit den verbleibenden Elementen generiert wird nacheinander, um eine maximale Heap-Sortierung zu erzeugen.

Heap-Sortierung

Generieren Sie eine ungeordnete Sequenz zu einem maximalen Heap und kombinieren Sie das oberste Element von der Heap mit Das letzte Element tauscht die Positionen und die verbleibenden Elemente werden generiert, um einen maximalen Heap zu generieren. Die Elemente werden nacheinander ausgetauscht und ein maximaler Heap wird generiert

Zeitkomplexität: O(NlogN) Raumkomplexität: O( 1)

Einführung:

Heap-Sortierung (englisch: Heapsort) bezieht sich auf einen Sortieralgorithmus, der unter Verwendung der Datenstruktur eines Heaps entwickelt wurde. Ein Heap ist eine Struktur, die sich einem vollständigen Binärbaum annähert und gleichzeitig die Heaping-Eigenschaft erfüllt: Das heißt, der Schlüsselwert oder Index eines untergeordneten Knotens ist immer kleiner (oder größer) als sein übergeordneter Knoten.

Heap-Operationen

In der Heap-Datenstruktur befindet sich der maximale Wert im Heap immer am Wurzelknoten (wenn der Heap in einer Prioritätswarteschlange verwendet wird, der minimale Wert im Heap). befindet sich am Wurzelknoten).

Die folgenden Operationen sind im Heap definiert:

Max Heapify: Passen Sie den untergeordneten Endknoten des Heaps so an, dass der untergeordnete Knoten immer kleiner als der übergeordnete Knoten ist

Max. Heap erstellen: Alle Daten im Heap neu anordnen

HeapSort: Entfernen Sie den Wurzelknoten der ersten Daten und führen Sie die rekursive Operation der maximalen Heap-Anpassung durch

Das obige ist der detaillierte Inhalt vonWas für eine Art ist die Heap-Sortierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!