Grundlegender Heapsort

1. Konzept und Einführung

Heapsort ist ein Sortieralgorithmus, der unter Verwendung der Heap-Datenstruktur entwickelt wurde.

Ein Heap ist eine Struktur, die einen vollständigen Binärbaum approximiert und gleichzeitig die Heap-Eigenschaft erfüllt: Das heißt, der Schlüssel oder Index eines Kindknotens ist immer kleiner (oder größer) als der seines Elternknotens.

II. Anwendungsanweisungen

Unser vorheriger Prozess zum Aufbau eines Heaps bestand darin, Daten nacheinander in den Heap einzufügen, indem die insert-Methode mit shift up aufgerufen wurde; die Zeitkomplexität dieses Algorithmus istO(nlogn), der in diesem Abschnitt vorgestellte Prozess zum Aufbau einer Heap-Sortierung heißtHeapify, die Zeitkomplexität des Algorithmus istO(n)。

III. Prozessdiagramm

Ein vollständiger Binärbaum hat eine wichtige Eigenschaft: Der Index des ersten Nicht-Blattknotens istn/2der durch Abrunden erhaltene Indexwert, wobeindie Anzahl der Elemente ist (unter der Annahme, dass Array-Indizes bei 1 beginnen).

Die Position an Index 5 ist der erste Nicht-Blattknoten. Ausgehend davon gehen wir eins nach dem anderen vor, wobei wir für jedes Element als Wurzelknoten die Shift-Down-Operation durchführen, um die Max-Heap-Eigenschaft zu erfüllen.

Nach der Shift-Down-Operation an Index 5 tauschen 22 und 62 ihre Positionen.

Führen Sie die Shift-Down-Operation für das Element an Index 4 durch.

Führen Sie die Shift-Down-Operation für das Element an Index 3 durch.

Führen Sie die Shift-Down-Operation für das Element an Index 2 durch.

Führen Sie schließlich die Shift-Down-Operation für den Wurzelknoten durch, und der gesamte Heapsort-Prozess ist abgeschlossen.

IV. Java-Beispielcode

Quellcode-Paket-Download:Download

Code der Datei src/example/heap/Heapify.java:

package example.heap;

import example.sort.SortTestHelper;

/**
* Verwenden Sie Heapify, um Heapsort durchzuführen
 */

public class Heapify<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Konstruktor, erstellt einen Max-Heap aus einem gegebenen Array
    // Der Prozess zum Aufbau des Heaps hat die Zeitkomplexität O(n)
    public Heapify(T arr[]){

        int n = arr.length;

        data = (T[])new Comparable[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;
        // Beginne beim ersten Element, das kein Blattknoten ist
        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }
    // Gibt die Anzahl der Elemente im Heap zurück
    public int size(){
        return count;
    }
    // Gibt einen booleschen Wert zurück, der angibt, ob der Heap leer ist
    public boolean isEmpty(){
        return count == 0;
    }
    // Ein neues Element item in den Max-Heap einfügen
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Das oberste Element aus dem Max-Heap entnehmen, d. h. das größte im Heap gespeicherte Datenelement
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // Oberstes Element des Max-Heaps abrufen
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }


    // Die beiden Elemente an den Indizes i und j im Heap vertauschen
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Kern-Hilfsfunktionen für den Max-Heap
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    private void shiftDown(int k){

        while( 2*k <= count ){
            int j = 2*k; // In dieser Schleifeniteration tauschen data[k] und data[j] die Positionen
            if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
                j ++;
            // data[j] ist das Maximum von data[2*k] und data[2*k+1]

            if( data[k].compareTo(data[j]) >= 0 ) break;
            swap(k, j);
            k = j;
        }
    }

    // Teste heapify
    public static void main(String[] args) {
        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        Heapify<Integer> heapify = new Heapify<Integer>(arr);
        // Daten in heapify schrittweise mit extractMax extrahieren
        // Die Entnahmereihenfolge sollte absteigend sein
        for( int i = 0 ; i < N ; i ++ ){
            arr[i] = heapify.extractMax();
            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