Heap Sorteeralgoritme (met code in Python en C++)

Wat is een heapsortalgoritme?

Heap Sort is een van de populaire en snellere sorteeralgoritmen. Het is gebouwd op de volledige datastructuur van de binaire boom. We zoeken naar het maximale element en plaatsen dit bovenaan voor de maximale heap. We plaatsen het op het bovenliggende knooppunt van de binaire boom.

Laten we zeggen dat er een array is gegeven, gegevens = [10,5, 7, 9, 4, 11, 45, 17, 60].

Als in de array de i-de (i=0,1,2,3 …) index een ouderknooppunt is, zullen (2i+1) en (2i+2) de linker en rechter kinderen zijn. Het creëren van een volledige binaire boom met deze array zal er als volgt uitzien:

Heap Sort-algoritme

Wij zullen de hij doenapify proces van het begin tot het einde van de array. Als we de array naar een boom converteren, ziet deze er in eerste instantie uit zoals hierboven. We kunnen zien dat er geen enkele heap-eigenschap wordt onderhouden (min-heap of max heap). We krijgen de gesorteerde array door de heapify proces voor alle knooppunten.

Toepassing van heapsortering

Hier is een voorbeeld van het gebruik van het heap sort-algoritme:

  • Voor de constructie van “prioriteitswachtrijen” is heap-sortering nodig. Omdat heapsort het element gesorteerd houdt nadat elke invoeging is gemaakt.
  • Heap Data Structure is efficiënt bij het vinden van de kth grootste element in een gegeven array.
  • Linux Kernel gebruikt standaard de heap-sortering sorteeralgoritme omdat het O (1) spatie com heeftplexheid.

Maak heapsortering met voorbeeld

Hier zullen we een maximale heap van de follo construerenwing complete binaire boom.

Maak heapsortering met voorbeeld

De bladknooppunten zijn 17, 60, 4, 11 en 45. Ze hebben geen onderliggende knooppunten. Daarom zijn het bladknopen. Dus we beginnen met de hijapify methode van hun ouderknooppunt. Hier zijn de stappen:

Stap 1) Selecteer de meest linkse subboom. Als de onderliggende knooppunten groter zijn, verwisselt u het bovenliggende knooppunt met het onderliggende knooppunt.

Hier is het ouderknooppunt 9. En de onderliggende knooppunten zijn 17 en 60. Omdat 60 het grootste is, worden 60 en 9 verwisseld om de maximale hoop.

Maak heapsortering met voorbeeld

Stap 2) Nu wordt de meest linkse subboom opgestapeld. Het volgende ouderknooppunt is 7. Dit ouderknooppunt heeft twee onderliggende knooppunten, en het grootste is 45. 45 en 7 worden dus verwisseld.

Maak heapsortering met voorbeeld

Maak heapsortering met voorbeeld

Stap 3) Knooppunten 60 en 4 hebben het bovenliggende knooppunt 5. Omdat “5” kleiner is dan het onderliggende knooppunt 60, zal deze worden verwisseld.

Maak heapsortering met voorbeeld

Maak heapsortering met voorbeeld

Stap 4) Nu heeft knooppunt 5 het onderliggende knooppunt 17,9. Hierdoor wordt de eigenschap max heap niet behouden. Dus 5 wordt vervangen door 17.

Maak heapsortering met voorbeeld

Stap 5) Knooppunt 10 wordt verwisseld met 60 en vervolgens verwisseld met 17. Het proces ziet er als volgt uit:wing.

Maak heapsortering met voorbeeld

Maak heapsortering met voorbeeld

Stap 6) Tot stap 5 hebben we de maximale heap gemaakt. Elk ouderknooppunt is groter dan zijn onderliggende knooppunten. Het hoofdknooppunt heeft de maximale waarde (60).

Opmerking: Om de gesorteerde array te maken, moeten we het knooppunt met de maximale waarde vervangen door zijn opvolger.

Dit proces heet “uittreksel max”. Omdat 60 het maximale knooppunt is, zullen we de positie ervan vastleggen op de 0e index en de heap maken zonder knooppunt 60.

Maak heapsortering met voorbeeld

Maak heapsortering met voorbeeld

Stap 7) Als 60 wordt verwijderd, is de volgende maximale waarde 45. We zullen het proces “Max extraheren” opnieuw uitvoeren vanaf knooppunt 45.

Deze keer krijgen we 45 en vervangen we het rootknooppunt door zijn opvolger 17.

We moeten presteren”Extraheer Max”Totdat alle elementen zijn gesorteerd.

Nadat we deze stappen hebben uitgevoerd totdat we alle maximale waarden hebben geëxtraheerd, krijgen we de volgende informatiewing matrix.

Maak heapsortering met voorbeeld

Wat is binaire heap?

Een binaire hoop is een soort compleet binaire boom data structuur. In dit soort boomstructuur is het ouderknooppunt groter of kleiner dan de onderliggende knooppunten. Als het bovenliggende knooppunt kleiner is, wordt de heap de “Min Heap” genoemd en als het bovenliggende knooppunt groter is, wordt de heap de “Max Heap” genoemd.

Hier volgen voorbeelden van min heap en max heap.

Min-hoop en Max-hoop
Min-hoop en Max-hoop

Als u in de bovenstaande afbeelding de “Min Heap” opmerkt, is het bovenliggende knooppunt altijd kleiner dan de onderliggende knooppunten. Aan de kop van de boom vinden we de kleinste waarde 10.

Op dezelfde manier is voor de “Max Heap” het bovenliggende knooppunt altijd groter dan de onderliggende knooppunten. Het maximale element is aanwezig op het hoofdknooppunt voor de “Max Heap”.

Wat is hijapify"?

"Hijapify” is het principe van de heap dat de positie van het knooppunt garandeert. In Hijapify, onderhoudt een max heap altijd een relatie met ouder en kind, en dat betekent dat het ouderknooppunt groter zal zijn dan de onderliggende knooppunten.

Als er bijvoorbeeld een nieuw knooppunt wordt toegevoegd, moeten we de heap opnieuw vormgeven. Het is echter mogelijk dat we de knooppunten moeten wijzigen of verwisselen of de array opnieuw moeten indelen. Dit proces van het hervormen van een hoop wordt het ‘hij’ genoemdapify'.

Hier is een voorbeeld van hoe hijapify werken:

Een nieuw knooppunt toevoegen en Heapify
Een nieuw knooppunt toevoegen en hijapify

Hier zijn de stappen voor hemapify:

Stap 1) Knooppunt 65 toegevoegd als het rechterkind van knooppunt 60.

Stap 2) Controleer of het nieuw toegevoegde knooppunt groter is dan het bovenliggende knooppunt.

Stap 3) Omdat het groter is dan het bovenliggende knooppunt, hebben we het juiste kind met het bovenliggende knooppunt geruild.

Hoe de hoop te bouwen

Voordat je de hoop bouwt of hijapify een boom, we moeten weten hoe we hem gaan opslaan. Omdat de heap een volledige binaire boom is, is het beter om een reeks om de gegevens van de heap vast te houden.

Laten we zeggen dat een array in totaal n elementen bevat. Als de “i”-index een ouderknooppunt is, bevindt het linkerknooppunt zich op de index (2i+1), en het rechterknooppunt bevindt zich op de index (2i+2). We gaan ervan uit dat de array-index begint vanaf 0.

Laten we hiermee een maximale heap opslaan in een array-achtige following:

Array-gebaseerde weergave van de Max Heap
Array-gebaseerde weergave van de maximale heap

De hijapify algoritme behoudt de heap-eigenschap. Als de ouder niet de extreme waarde heeft (kleiner of groter), wordt deze verwisseld met het meest extreme onderliggende knooppunt.

Hier zijn de stappen naar hijapify een maximale hoop:

Stap 1) Begin vanaf het bladknooppunt.

Stap 2) Zoek het maximum tussen de ouder en de kinderen.

Stap 3) Verwissel de knooppunten als het onderliggende knooppunt een grotere waarde heeft dan het bovenliggende knooppunt.

Stap 4) Ga een niveau hoger.

Stap 5) Volg stappen 2,3,4 totdat we index 0 bereiken of de hele boom sorteren.

Hier is de pseudocode voor recursieve hijapify (max. hoop):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Pseudocode voor heapsortering

Hier is de pseudocode voor het heap sort-algoritme:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Voorbeeld van heap-sorteercode in C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Output:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Voorbeeld van heap-sorteercode in Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Output:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Tijd en ruimte Complexiteitsanalyse van Heap Sort

Er is tijd complexity en Space complexdie we kunnen analyseren voor de heap-soort. Voor tijd complexWij hebben het volgendewing gevallen:

  1. Beste geval
  2. Gemiddeld geval
  3. Het slechtste geval

De heap wordt geïmplementeerd op een volledige binaire boom. Op het onderste niveau van de binaire boom bevindt zich dus het maximale aantal knooppunten. Als het onderste niveau n knooppunten heeft, zal het bovenste niveau n/2 knooppunten hebben.

Tijd en ruimte Complexiteitsanalyse

In dit voorbeeld heeft niveau 3 vier items, niveau 2 twee items en niveau 1 één item. Als er in totaal n items zijn, is de hoogte of het totale niveau hetzelfde Log2(N). Het invoegen van een enkel element kan dus maximaal Log(n)-iteraties vergen.

Als we de maximale waarde uit de heap willen halen, nemen we gewoon het rootknooppunt. Voer dan opnieuw de hij uitapify. Ieder hijapify neemt Log2(N) tijd. Het extraheren van het maximum kost O(1) tijd.

Best Case Time Complexity voor Heap Sort-algoritme

Als alle elementen al in de array zijn gesorteerd, kost het O(n) tijd om de heap op te bouwen. Omdat als de lijst gesorteerd is, het invoegen van een item de constante tijd zal duren die O(1) is.

In het beste geval kost het dus O(n) tijd om een ​​max-heap of min-heap te maken.

Gemiddelde casustijd Complexity voor Heap Sort-algoritme

Het invoegen van een item of het extraheren van een maximum kost O(log(n)) tijd. Dus de gemiddelde zaaktijd complexity voor het heap sort-algoritme is O(n logboek(n)).

Worst Case Tijd Complexity voor Heap Sort-algoritme

Net als in het gemiddelde geval zouden we in het slechtste geval misschien wel de uitvoering kunnen uitvoerenapify n keer. Ieder hijapify kost O(log(n)) tijd. Dus in het ergste geval complexzal zijn O(n logboek(n)).

Ruimte Complexity voor Heap Sort-algoritme

Heap sort is een ter plekke ontworpen algoritme. Dit betekent dat er geen extra of tijdelijk geheugen nodig is om de taak uit te voeren. Als we de implementatie zien, zullen we merken dat we swap () hebben gebruikt om de uitwisseling van de knooppunten uit te voeren. Er was geen andere lijst of array nodig. Dus de ruimte complexiteit is O(1).