Heap-Sortieralgorithmus

Heap Sort, сортировка, алгоритмы

Heap Sort ist ein beliebter und effizienter Sortieralgorithmus in der Computerprogrammierung. Zu lernen, wie man einen Heap-Sortieralgorithmus schreibt, erfordert Kenntnisse über zwei Arten von Datenstrukturen - Arrays und Bäume.

Zum Beispiel wird der erste Satz von Zahlen, die wir sortieren möchten, im Array [10, 3, 76, 34, 23, 32] gespeichert, und nach dem Sortieren erhalten wir ein sortiertes Array [3,10,23,32, 34,76].

Die Heap-Sortierung funktioniert, indem die Elemente eines Arrays als eine spezielle Art eines vollständigen Binärbaums, der als Heap bezeichnet wird, dargestellt werden.

Was ist ein binärer Baum? Welche Arten von Binärbäumen gibt es?

Binärbaum ist eine Baumdatenstruktur, in der jeder Elternknoten höchstens zwei Kinder haben kann.

Ein vollständiger Binärbaum ist eine spezielle Art von Binärbaum, bei dem jeder Elternknoten zwei oder keine Kinder hat.

Der Perfekte Binärbaum ähnelt dem Vollständigen Binärbaum, jedoch mit zwei Hauptunterschieden:

1. Jedes Level muss komplett ausgefüllt werden.
2. Alle Blattelemente sollten sich nach links neigen.

Hinweis: Das letzte Element darf kein gültiges Geschwister haben, d. h. ein idealer Binärbaum muss kein vollständiger Binärbaum sein.

Wie erstelle ich einen vollständigen Binärbaum aus einer unsortierten Liste (Array)?

• Wählen Sie das erste Element der Liste als Wurzelknoten aus. (Erste Ebene - 1 Element).
• Platzieren Sie das zweite Element als linkes Kind des Wurzelknotens und das dritte Element als rechtes Kind. (Zweite Ebene - 2 Elemente).
• Platzieren Sie die folgenden beiden Elemente als untergeordnete Elemente des linken Knotens der zweiten Ebene. Platzieren Sie erneut die nächsten beiden Elemente als Kinder des rechten Knotens der zweiten Ebene (3. Ebene - 4 Elemente).
• Wiederholen Sie den Vorgang, bis Sie das letzte Element erreicht haben.

Beziehung zwischen Array-Indizes und Baumelementen

Ein vollständiger Binärbaum hat eine interessante Eigenschaft, die wir verwenden können, um die Kinder und Eltern eines beliebigen Knotens zu finden.
Wenn der Index eines beliebigen Elements im Array i ist, wird das Element am Index 2i + 1 zum linken untergeordneten Element und das Element am Index 2i + 2 zum rechten untergeordneten Element. Außerdem wird dem übergeordneten Element eines Elements am Index i eine untere Grenze von (i-1) / 2 gegeben.

Lass es uns überprüfen:

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

Bestätigen Sie auch, dass die Regeln zum Auffinden des übergeordneten Knotens korrekt sind:

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

Das Verständnis dieser Zuordnung von Array-Indizes zu Baumpositionen ist entscheidend, um zu verstehen, wie die Heap-Datenstruktur funktioniert und wie sie zur Implementierung der Heap-Sortierung verwendet wird.

Was ist eine Heap-Datenstruktur?

Ein Heap ist eine spezielle baumartige Datenstruktur. Man sagt, dass ein Binärbaum einer Heap-Datenstruktur folgt, wenn

• Dies ist ein vollständiger Binärbaum;
• alle Knoten im Baum folgen der Eigenschaft, dass sie größer als ihre Kinder sind, d.h. das größte Element ist die Wurzel und beide seiner Kinder sind kleiner als die Wurzel, und so weiter. Ein solcher Heap wird als absteigender Heap (Max-Heap) bezeichnet. Wenn stattdessen alle Knoten kleiner als ihre Kinder sind, spricht man von einem wachsenden Heap (Min-Heap).

Links in der Abbildung ist ein abnehmender Haufen, rechts ein zunehmender Haufen.

Wie man einen Baum baut

Beginnend mit einem perfekten Binärbaum können wir ihn in einen absteigenden Baum ändern, indem wir die Heapify-Funktion für alle Nicht-Blatt-Elemente des Heaps ausführen.

Da heapfiy Rekursion verwendet, kann dies schwer zu verstehen sein. Lassen Sie uns also zuerst darüber nachdenken, wie Sie einen Baum mit drei Elementen erstellen würden.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

Das obige Beispiel zeigt zwei Szenarien – eines, in dem die Wurzel das größte Element ist und wir nichts tun müssen. Und eine andere, bei der die Wurzel ein größeres Kind hat und wir sie austauschen mussten, um das Eigentum des schrumpfenden Haufens zu behalten.
Wenn Sie zuvor mit rekursiven Algorithmen gearbeitet haben, verstehen Sie, dass dies der Basisfall sein sollte.

Stellen wir uns nun ein anderes Szenario vor, in dem es mehr als eine Ebene gibt.

In der Abbildung sind bereits beide Teilbäume des Wurzelelements der zweiten Ebene
absteigende Haufen.
Das oberste Element passt nicht in den absteigenden Haufen, aber alle Teilbäume sind absteigend.
Um die absteigende Eigenschaft für den gesamten Baum beizubehalten, müssen wir das übergeordnete Element nach unten "drücken", bis es seine korrekte Position erreicht.

Um also die absteigende Eigenschaft in einem Baum beizubehalten, in dem beide Teilbäume absteigend sind, müssen wir wiederholt heapify für das Wurzelelement ausführen, bis es größer als seine Kinder ist oder zu einem Blattknoten wird.

Wir können diese beiden Bedingungen wie folgt in einer einzigen Heapify-Funktion kombinieren:

void heapify(int arr[], int n, int i)
{
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   if (largest != i)
   {
     swap(arr[i], arr[largest]);

     // Recursively heapify the affected sub-tree
     heapify(arr, n, largest);
   }
}

Diese Funktion funktioniert sowohl für den Basisfall als auch für jede Baumgröße. Daher können wir das Wurzelelement an die richtige Position verschieben, um einen schrumpfenden Heap-Status für jede Baumgröße aufrechtzuerhalten, solange die Teilbäume schrumpfen.

Absteigender Haufenaufbau

Um einen absteigenden Heap aus einem beliebigen Baum zu erstellen, können wir mit dem Erstellen jedes Unterbaums von unten nach oben beginnen und einen absteigenden Heap erhalten, nachdem wir die Funktion auf alle Elemente angewendet haben, einschließlich des Wurzelelements.

Im Fall eines vollständigen Baums ist der erste Index eines Nicht-Blattknotens als n/2 – 1 definiert. Alle anderen Knoten danach sind Blattknoten und benötigen daher keinen Heap.

Wir können einen absteigenden Haufen wie folgt bauen:

// Build heap (rearrange array)
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

Wie im obigen Diagramm gezeigt, beginnen wir mit einem Haufen der kleinsten Bäume und arbeiten uns nach oben, bis wir das Wurzelelement erreichen.

Verfahren für Heapsort

1. Da der Baum die absteigende Eigenschaft erfüllt, wird das größte Element am Wurzelknoten gespeichert.
2. Entfernen Sie das Wurzelelement und platzieren Sie es am Ende des Arrays (n-te Position). Platzieren Sie das letzte Element des Baums (den Haufen) im freien Raum.
3. Verringern Sie die Heap-Größe um 1 und vergrößern Sie das Wurzelelement erneut, sodass Sie das größte Element an der Wurzel haben.
4. Der Vorgang wird wiederholt, bis alle Elemente der Liste sortiert sind.

Der Code sieht so aus:

for (int i=n-1; i>=0; i--)
   {
     // Переместить текущий корень в конец
     swap(arr[0], arr[i]);

     // вызовите максимальный heapify на уменьшенной куче
     heapify(arr, i, 0);
   }

Leistung

Die Heap-Sortierung hat für alle Fälle (bester Fall, durchschnittlicher Fall und schlimmster Fall) eine Zeitkomplexität von O(nlogn). Was ist der Grund? Die Höhe eines vollständigen Binärbaums mit n Elementen ist log(n).

Wie wir zuvor gesehen haben, müssen wir, um ein Element, dessen Teilbäume bereits absteigende Haufen sind, vollständig zu akkumulieren, das Element mit seinen linken und rechten Kindern vergleichen und es nach unten drücken, bis es einen Punkt erreicht, an dem beide seiner Kinder kleiner sind als es.

Im schlimmsten Fall müssten wir ein Element vom Wurzelknoten zum Blattknoten verschieben, indem wir mehrere log(n)-Vergleiche und -Swaps durchführen.

Im build_max_heap-Schritt tun wir dies für n/2 Elemente, sodass die Worst-Case-Komplexität des build_heap-Schritts n/2 * log(n) ~ nlogn ist.

Im Sortierschritt tauschen wir das Wurzelelement mit dem letzten Element aus und vertauschen das Wurzelelement. Für jedes Element dauert dies wiederum lange, da wir dieses Element möglicherweise von der Wurzel zum Blatt verschieben müssen. Da wir die Operation n-mal wiederholen, ist der Schritt heap_sort auch nlogn.

Da die Schritte build_max_heap und heap_sort nacheinander ausgeführt werden, wird die algorithmische Komplexität nicht multipliziert und bleibt in der Größenordnung von nlogn.

Es sortiert auch im O(1)-Komplexitätsraum. Im Vergleich zu Quicksort, Worst Case (O(nlogn)). Quicksort hat im schlimmsten Fall eine Komplexität von O (n ^ 2). Aber in anderen Fällen ist Quicksort ziemlich schnell. Introsort ist eine Alternative zu Heapsort, die Quicksort und Heapsort kombiniert, um Vorteile wie die Worst-Case-Geschwindigkeit von Heapsort und die Durchschnittsgeschwindigkeit von Quicksort beizubehalten.

Heap-Sortierung verwenden

Sicherheitsbezogene und eingebettete Systeme wie der Linux-Kernel verwenden Heapsort aufgrund der Obergrenze von O (n log n) für die Laufzeit von Heapsort und der konstanten Obergrenze von O (1) für seinen Sicherungsspeicher.

Obwohl Heapsort selbst im schlimmsten Fall eine Zeitkomplexität von O (n log n) hat, hat es nicht mehr Anwendungen (im Vergleich zu anderen Sortieralgorithmen wie Quicksort, Mergesort). Die zugrunde liegende Datenstruktur, der Heap, kann jedoch effektiv verwendet werden, wenn wir das kleinste (oder größte) aus einer Liste von Elementen extrahieren möchten, ohne den Aufwand, die verbleibenden Elemente in sortierter Reihenfolge zu halten. Zum Beispiel Prioritätswarteschlangen.

Implementierung von Heap Sort in verschiedenen Programmiersprachen

C++-Implementierung

// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i)
{
   // Find largest among root, left child and right child
   int largest = i;
   int l = 2*i + 1;
   int r = 2*i + 2;

   if (l < n && arr[l] > arr[largest])
     largest = l;

   if (right < n && arr[r] > arr[largest])
     largest = r;

   // Swap and continue heapifying if root is not largest
   if (largest != i)
   {
     swap(arr[i], arr[largest]);
     heapify(arr, n, largest);
   }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
   // Build max heap
   for (int i = n / 2 - 1; i >= 0; i--)
     heapify(arr, n, i);

   // Heap sort
   for (int i=n-1; i>=0; i--)
   {
     swap(arr[0], arr[i]);

     // Heapify root element to get highest element at root again
     heapify(arr, i, 0);
   }
}

void printArray(int arr[], int n)
{
   for (int i=0; i<n; ++i)
     cout << arr[i] << " ";
   cout << "\n";
}

int main()
{
   int arr[] = {1,12,9,5,6,10};
   int n = sizeof(arr)/sizeof(arr[0]);
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

Java-Implementierung

// Java program for implementation of Heap Sort
public class HeapSort
{   

    public void sort(int arr[])
    {
        int n = arr.length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
          heapify(arr, n, i);
        }


        // Heap sort
        for (int i=n-1; i>=0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify root element
            heapify(arr, i, 0);
        }
    }

    void heapify(int arr[], int n, int i)
    {
        // Find largest among root, left child and right child
        int largest = i; 
        int l = 2*i + 1; 
        int r = 2*i + 2;  

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Swap and continue heapifying if root is not largest
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i < n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void main(String args[])
    {
        int arr[] = {1,12,9,5,6,10};

        HeapSort hs = new HeapSort();
        hs.sort(arr);

        System.out.println("Sorted array is");
        printArray(arr);
    }
}

Python-Implementierung (Python 3)

def heapify(arr, n, i):
    # Find largest among root and children
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2 

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # If root is not largest, swap with largest and continue heapifying
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # Build max heap
    for i in range(n, 0, -1):
        heapify(arr, n, i)


    for i in range(n-1, 0, -1):
        # swap
        arr[i], arr[0] = arr[0], arr[i]  

        #heapify root element
        heapify(arr, i, 0)


arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
    print ("%d" %arr[i])