Optimierung von Heap Sort
Im Heap-Sort aus dem vorherigen Abschnitt haben wir zusätzlichen Speicherplatz zugewiesen, um den Heap aufzubauen und ihn zu sortieren. In diesem Abschnitt optimieren wir dies durch die Verwendung von In-Place-Heap-Sort.
Bei einem Max-Heap werden zuerst die Daten an der Startposition mit dem Wert am Ende des Arrays vertauscht, sodass das Ende des Arrays zum maximalen Element wird. Dann wird eine Shift-Down-Operation auf Element W ausgeführt, um den Max-Heap wiederherzustellen. Als Nächstes wird der neu erzeugte Maximalwert mit der vorletzten Position des gesamten Arrays vertauscht, sodass die vorletzte Position den zweitgrößten Wert enthält. Dieser Prozess wird analog fortgesetzt.
Der gesamte Prozess kann durch das folgende Diagramm veranschaulicht werden:

Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Code der Datei src/example/heap/HeapSort.java:
import example.sort.SortTestHelper;
/**
* In-Place-Heapsort
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// Beachten Sie, dass unser Heap an diesem Punkt ab 0 indiziert wird
// Beginne bei (Index des letzten Elements - 1) / 2
// Der Index des letzten Elements ist n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// Die beiden Elemente an den Indizes i und j im Heap vertauschen
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
// Ursprünglicher shiftDown-Prozess
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
// Linker Kindknoten
int j = 2 * k + 1;
// Der rechte Kindknoten ist größer als der linke Kindknoten
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
// Größer als beide Kindknoten
if (arr[k].compareTo(arr[j]) >= 0) break;
// Werte des ursprünglichen Knotens und des Kindknotens vertauschen
swap(arr, k, j);
k = j;
}
}
// HeapSort testen
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// Daten in heapify schrittweise mit extractMax extrahieren
// Die Entnahmereihenfolge sollte absteigend sein
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
}
// Sicherstellen, dass das arr-Array absteigend sortiert ist
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}
}