Sortieralgorithmen: Heap sort

Eine weitere Kategorie von Sortieralgorithmen sind solche, die ein Array/eine Liste als eine Baumstruktur darstellen. Dabei wird ein Element als ein Knoten (Eltern) betrachtet und seine Verzweigungen als Söhne (Kindsknoten) . Bei dem Heap sort kann jeder Knoten ein oder zwei Söhne haben. Sollte ein Knoten keine Verzweigung haben, so wird dieser als ein Blatt bezeichnet. Ein Blatt ist somit das letzte Element des jeweiligen Pfades, vom Knoten ausgehend.

Abbildung: Liste als Baumstruktur

Natürlich ist und bleibt die zugrundeliegende Datenstruktur eine Liste. Allerdings gibt es eine Formel, um herauszufinden zu welchem Knoten welche Söhne gehören. Damit kann man bspw. den rechten Sohn mit dem linken Sohn vertauschen oder den linken Sohn mit dem Elternknoten. Der Heap sort benutzt diese Technik zum sortieren von Elementen.

Beispiel
Eine Liste hat 20 Indizes. Man nehme den vierten Index. Mit folgender Formel kann man seine Söhne bestimmen.
linker Sohn : 2 * index+1
rechter Sohn : 2 * index+2
Der linke Sohn hat somit den Indexwert 2 * 4+1=9 und der rechte Sohn den Indexwert 2 * 4+2=10.

• Heap sort (c++)

#include <iostream> 

void swapElement(int &x, int &y){
    int temp = x;
    x = y;
    y = temp;
}

void reheap(int list[], int n, int i) { 
    int largest = i; // largest is root
    int left= 2*i + 1; // left index
    int right= 2*i + 2; // right index
  
    // left child is larger than root
    if (left < n && list[left] > list[largest]) {
        largest = left;
    }
  
    // right child is larger than root
    if (right < n && list[right] > list[largest]) {
        largest = right;
    }
  
    // largest is not root 
    if (largest != i) { 
        swapElement(list[i], list[largest]); 
        reheap(list, n, largest); 
    } 
} 
  
void heapSort(int list[], int n) { 
    for(int i = n / 2 - 1; i >= 0; i--){ 
        reheap(list, n, i);
    }

    for(int i=n-1; i>=0; i--) { 
        swapElement(list[0], list[i]); 
        reheap(list, i, 0); 
    } 
}
  
int main()  { 
    const unsigned int SIZE = 10;
    int list[SIZE] = {12, 1, 11, 4, 13, 5, 6, 7, 0, 33}; 
    heapSort(list, SIZE);
    
    for(int res = 0; res < 10;res++){
        std::cout << list[res] << "\n";
    }
}

Quellen
Abbildung: www.aallegranzi.com/wp-content/uploads/2019/07/c9fa843.png
https://www.researchgate.net/publication/320715254_Heap_Sorting_Based_on_Array_Sorting [letzter Zugriff: 10.02.2020, 17:40]