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:

package example.heap;

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];
    }
}
Weitere Erweiterungen