Heap sorteeralgoritme (met code in Python en C++)
Sara Chen
Wat is een heapsortalgoritme?
Heap Sort is een van de populaire en snellere sorteeralgoritmen. Het is gebouwd op de volledige binaire boomdatastructuur. We zoeken naar het maximale element en plaatsen het bovenaan voor de maximale heap. We plaatsen het op de bovenliggende knoop 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:
We zullen het heapify-proces uitvoeren van het begin tot het einde van de array. Als we de array in eerste instantie converteren naar een boom, zal het eruit zien zoals hierboven. We kunnen zien dat het geen heap-eigenschap (min-heap of max heap) onderhoudt. We zullen de gesorteerde array verkrijgen door het heapify-proces uit te voeren voor alle nodes.
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 een ruimtecomplexiteit van O (1) heeft.
Maak heapsortering met voorbeeld
Hier construeren we een maximale heap uit de volgende complete binaire boom.
De leaf nodes zijn 17, 60, 4, 11 en 45. Ze hebben geen child nodes. Daarom zijn het leaf nodes. Dus we starten de heapify-methode vanaf hun parent node. Dit 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.
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.
Stap 3) Knooppunten 60 en 4 hebben het bovenliggende knooppunt 5. Omdat “5” kleiner is dan het onderliggende knooppunt 60, zal deze worden verwisseld.
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.
Stap 5) Knooppunt 10 wordt omgewisseld met 60 en vervolgens met 17. Het proces ziet er als volgt uit.
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.
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 matrix.
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.
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 “Heapify”?
“Heapify” is het principe van de heap dat de positie van de node verzekert. In Heapify onderhoudt een max heap altijd een relatie met parent en child, en dat wil zeggen dat de parent node groter zal zijn dan de child nodes.
Als er bijvoorbeeld een nieuwe node wordt toegevoegd, moeten we de heap opnieuw vormgeven. Het kan echter nodig zijn om de nodes te wijzigen of te verwisselen of de array opnieuw te rangschikken. Dit proces van het opnieuw vormgeven van een heap wordt de "heapify" genoemd.
Hier is een voorbeeld van hoe heapify werkt:
Dit zijn de stappen voor heapify:
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 we de heap bouwen of een heapify-tree maken, moeten we weten hoe we deze gaan opslaan. Omdat de heap een complete binaire tree 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.
Hiermee kunnen we een maximale heap opslaan in een array-achtige vorm:
Het heapify-algoritme behoudt de heap-eigenschap. Als de parent niet de extreme waarde heeft (kleiner of groter), wordt deze verwisseld met de meest extreme child node.
Dit zijn de stappen om een maximale heap te heapen:
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 heapify (max heap):
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 ruimtecomplexiteitsanalyse van Heap Sort
Er is tijdcomplexiteit en ruimtecomplexiteit die we kunnen analyseren voor de heap sort. Voor tijdcomplexiteit hebben we de volgende gevallen:
- Beste geval
- Gemiddeld geval
- 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.
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 de root node. Voer vervolgens heapify uit. Elke heapify neemt Log2(N) tijd. Het extraheren van het maximum kost O(1) tijd.
Beste case-tijdcomplexiteit voor heap-sorteeralgoritme
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 case-tijdcomplexiteit voor heap-sorteeralgoritme
Het invoegen van een item of het extraheren van een maximum kost O(log(n)) tijd. De gemiddelde case-tijdcomplexiteit voor het heap sort-algoritme is dus O(n logboek(n)).
Worst Case Tijd Complexiteit voor Heap Sort Algoritme
Vergelijkbaar met het gemiddelde geval, in het worst-case scenario, zouden we heapify n keer kunnen uitvoeren. Elke heapify kost O(log(n)) tijd. Dus, de worst-case tijdcomplexiteit zal zijn O(n logboek(n)).
Ruimtecomplexiteit voor heap-sorteeralgoritme
Heap sort is een in-place ontworpen algoritme. Dit betekent dat er geen extra of tijdelijk geheugen nodig is om de taak uit te voeren. Als we de implementatie bekijken, zullen we opmerken dat we swap() hebben gebruikt om de uitwisseling van de nodes uit te voeren. Er was geen andere lijst of array nodig. Dus de ruimtecomplexiteit is O(1).
