Heap Sort-algoritm (med Code in 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ädstrukturen. Vi kommer att söka efter det maximala elementet och placera det högst upp för den maximala heapen. Vi kommer att placera det på den överordnade noden i 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 k^th 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).

Obs: För att skapa den sorterade arrayen måste vi ersätta den maxvärdade noden med dess efterföljare.

Denna process kallas "extract-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 blir nästa maximala värde 45. Vi utför processen "Ex.tract 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"Extract Max” tills alla element är sorterade.

Efter att ha gjort dessa steg tills vi extracMed 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.

Om till exempel en ny nod läggs till måste vi omforma heapen. Vi kan dock behöva ändra eller byta ut noderna eller ordna om arrayen. Denna process av omformningping en heap 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)

Pseudo Code för högsortering

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å heapsortering Code 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å heapsortering Code 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:

1. Bästa fall
2. Genomsnittligt fall
3. 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 Logga₂(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 Logga₂(N) tid. Ex.tracAtt nå maximum 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

Sätta in ett objekt eller exempeltracatt beräkna en maximal kostnad O(log(n)) tid. Så den genomsnittliga tidskomplexiteten 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).

Vanliga frågor