Heap Sort Algorithm (med kod i Python och C++)
Vad är Heap Sort Algorithm?
Heap Sort är en av de populära och snabbare sorteringsalgoritmerna. Den är byggd på den kompletta binära träddatastrukturen. Vi kommer att söka efter det maximala elementet och lägga det överst för maxhögen. Vi kommer att placera den på föräldranoden för det binära trädet.
Låt oss säga att en array ges, data = [10,5, 7, 9, 4, 11, 45, 17, 60].
I arrayen, om i-th (i=0,1,2,3 …) index är en överordnad nod så kommer (2i+1) och (2i+2) att vara vänster och höger barn. Att skapa ett komplett binärt träd med denna array kommer att se ut så här:
Vi kommer att göra heapify-processen från början till slutet av arrayen. Till en början, om vi konverterar arrayen till ett träd, kommer den att se ut som ovan. Vi kan se att det inte upprätthåller någon heap-egenskap (min-heap eller max heap). Vi kommer att få den sorterade arrayen genom att göra heapify-processen för alla noder.
Tillämpning av Heap Sort
Här är lite användning av heap-sorteringsalgoritmen:
- Konstruktion av "prioriterade köer" behöver sorteras i högar. Eftersom heapsort håller elementet sorterat efter varje insättning görs.
- Heap Data Structure är effektiv för att hitta kth största elementet i en given array.
- Linux Kernel använder högsorteringen som standard sorteringsalgoritm eftersom det har O (1) rymdkomplexitet.
Skapa högsortering med exempel
Här kommer vi att konstruera en maxhög från följande kompletta binära träd.
Bladnoderna är 17, 60, 4, 11 och 45. De har inga barnnoder. Det är därför de är lövnoder. Så vi kommer att starta heapify-metoden från deras överordnade nod. Här är stegen:
Steg 1) Välj underträdet längst till vänster. Om de underordnade noderna är större, byt ut den överordnade noden med den underordnade noden.
Här är föräldernoden 9. Och de underordnade noderna är 17 och 60. Eftersom 60 är den största kommer 60 och 9 att bytas ut för att bibehålla max hög.
Steg 2) Nu är underträdet längst till vänster högt upp. Nästa föräldernod är 7. Denna förälder har två underordnade noder, och den största är 45. Så 45 och 7 kommer att bytas.
Steg 3) Noderna 60 och 4 har föräldranoden 5. Eftersom "5" är mindre än den underordnade noden 60 kommer den att bytas.
Steg 4) Nu har nod 5 den underordnade noden 17,9. Detta bibehåller inte egenskapen max heap. Så 5 kommer att ersättas med 17.
Steg 5) Nod 10 kommer att bytas ut med 60 och sedan bytas ut mot 17. Processen kommer att se ut som följande.
Steg 6) Fram till steg 5 skapade vi maxhögen. Varje föräldernod är större än dess underordnade noder. Rotnoden har maxvärdet (60).
Notera: För att skapa den sorterade arrayen måste vi ersätta den maxvärdade noden med dess efterföljare.
Denna process kallas "extrakt max”. Eftersom 60 är maxnoden fixar vi dess position till det 0:e indexet och skapar högen utan nod 60.
Steg 7) När 60 tas bort är nästa maxvärde 45. Vi kommer att göra processen "Extrahera Max" igen från nod 45.
Den här gången får vi 45 och ersätter rotnoden med dess efterföljare 17.
Vi måste prestera"Extrahera Max” tills alla element är sorterade.
Efter att ha gjort dessa steg tills vi extraherar alla maxvärden får vi följande array.
Vad är Binary Heap?
En binär hög är ett slags komplett binärt träd datastruktur. I denna typ av trädstruktur är föräldernoden antingen större eller mindre än undernoderna. Om föräldernoden är mindre kallas högen "Min Heap" och om föräldernoden är större kallas högen för "Max Heap".
Här är exempel på min heap och max heap.

I figuren ovan, om du märker "Min Heap", är föräldernoden alltid mindre än dess underordnade noder. I toppen av trädet kan vi hitta det minsta värdet 10.
På samma sätt, för "Max Heap", är den överordnade noden alltid större än de underordnade noderna. Det maximala elementet finns vid huvudnoden för "Max Heap".
Vad är "Heapify"?
"Heapify" är principen för heapen som säkerställer nodens position. I Heapify upprätthåller en maxhög alltid en relation med förälder och barn, och det är att föräldernoden kommer att vara större än undernoderna.
Till exempel, om en ny nod läggs till måste vi omforma högen. Däremot kan vi behöva ändra eller byta noder eller ordna om arrayen. Denna process att omforma en hög kallas "heapify".
Här är ett exempel på hur heapify fungerar:

Här är stegen för heapify:
Steg 1) Lade till nod 65 som rätt underordnad till nod 60.
Steg 2) Kontrollera om den nyligen tillagda noden är större än den överordnade.
Steg 3) Eftersom den är större än föräldernoden bytte vi rätt barn med dess förälder.
Hur man bygger högen
Innan vi bygger högen eller förhöjer ett träd måste vi veta hur vi ska lagra det. Eftersom högen är ett komplett binärt träd, är det bättre att använda en array för att hålla data från högen.
Låt oss säga att en array innehåller totalt n element. Om "i":e index är en överordnad nod, kommer den vänstra noden att vara vid index (2i+1), och den högra noden kommer att vara vid index (2i+2). Vi antar att arrayindexet börjar från 0.
Med detta, låt oss lagra en maxhög till en array-liknande följande:

Heapify-algoritmen upprätthåller heap-egenskapen. Om föräldern inte har det extrema värdet (mindre eller större), kommer det att bytas ut mot den mest extrema barnnoden.
Här är stegen för att heapify en maxhög:
Steg 1) Börja från lövnoden.
Steg 2) Hitta det maximala mellan förälder och barn.
Steg 3) Byt noderna om den underordnade noden har ett större värde än den överordnade.
Steg 4) Gå en nivå upp.
Steg 5) Följ steg 2,3,4 tills vi når index 0 eller sortera hela trädet.
Här är pseudokoden för rekursiv 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)
Pseudokod för heapsortering
Här är pseudokoden för heap-sorteringsalgoritmen:
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)
Exempel på heapsorteringskod 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); }
Produktion:
Initial Array: 10 5 7 9 4 11 45 17 60 Sorted Array (descending order): 60 45 17 11 10 9 7 5 4
Exempel på heapsorteringskod 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)
Produktion:
Initial List: 10 5 7 9 4 11 45 17 60 After HeapSort: 60 45 17 11 10 9 7 5 4
Tid och rumskomplexitetsanalys av Heap Sort
Det finns tidskomplexitet och rymdkomplexitet som vi kan analysera för högen. För tidskomplexitet har vi följande fall:
- Bästa fall
- Genomsnittligt fall
- Värsta fall
Högen är implementerad på ett komplett binärt träd. Så på den nedre nivån av det binära trädet kommer det att finnas det maximala antalet noder. Om bottennivån har n noder, kommer nivån ovan att ha n/2 noder.
I det här exemplet har nivå 3 fyra föremål, nivå 2 har två föremål och nivå 1 har ett föremål. Om det finns totalt n antal objekt kommer höjden eller totalnivån att vara Logga2(n). Så att infoga ett enda element kan ta maximalt med Log(n) iterationer.
När vi vill ta maxvärdet från högen tar vi bara rotnoden. Sedan igen, kör heapify. Varje heapify tar Logga2(N) tid. Att extrahera det maximala tar O(1) tid.
Bästa fall tidskomplexitet för Heap Sort Algorithm
När alla element redan är sorterade i arrayen kommer det att ta O(n) tid att bygga högen. För om listan är sorterad kommer att infoga ett objekt ta den konstanta tiden som är O(1).
Så det kommer att ta O(n) tid att skapa en max-hög eller min-hög i bästa fall.
Genomsnittlig falltidskomplexitet för heapsorteringsalgoritm
Att infoga en artikel eller extrahera en maximal kostnad O(log(n)) tid. Så, den genomsnittliga falltidskomplexiteten för heapsorteringsalgoritmen är O(n log(n)).
Worst Case Time Complexity for Heap Sort Algorithm
I likhet med det genomsnittliga fallet, i det värsta scenariot, skulle vi kunna utföra heapify n gånger. Varje heapify kommer att kosta O(log(n)) tid. Så den värsta tidskomplexiteten kommer att vara O(n log(n)).
Space Complexity for Heap Sort Algorithm
Heap sort är en platsdesignad algoritm. Detta innebär att inget extra eller tillfälligt minne behövs för att utföra uppgiften. Om vi ser implementeringen kommer vi att märka att vi använde swap () för att utföra utbytet av noderna. Ingen annan lista eller array behövdes. Så rymdkomplexiteten är O(1).