Heap Sort Algoritme (med kode i Python og C++)

Hva er Heap Sort Algorithm?

Heap Sort er en av de populære og raskere sorteringsalgoritmene. Den er bygget på den komplette binære tredatastrukturen. Vi vil søke etter det maksimale elementet og legge det på toppen for maksimalt haug. Vi vil sette den på foreldrenoden til det binære treet.

La oss si at en matrise er gitt, data = [10,5, 7, 9, 4, 11, 45, 17, 60].

I matrisen, hvis i-th (i=0,1,2,3 …) indeks er en overordnet node, vil (2i+1) og (2i+2) være venstre og høyre barn. Å lage et komplett binært tre med denne matrisen vil se slik ut:

Vi vil gjøre heapify-prosessen fra begynnelsen til slutten av matrisen. Til å begynne med, hvis vi konverterer matrisen til et tre, vil den se ut som ovenfor. Vi kan se at den ikke opprettholder noen heap-egenskap (min-heap eller max-heap). Vi vil få den sorterte matrisen ved å gjøre heapify-prosessen for alle nodene.

Anvendelse av Heap Sort

Her er litt bruk av heap-sorteringsalgoritmen:

Konstruksjon av "Prioritetskøer" trenger massevis. Fordi heapsort holder elementet sortert etter hver innsetting.
Heap Data Structure er effektiv for å finne k^th største element i en gitt matrise.
Linux Kernel bruker heap-sortering som standard sorteringsalgoritme ettersom den har O (1) romkompleksitet.

Lag haugsortering med eksempel

Her vil vi konstruere en maksimal haug fra følgende komplette binære tre.

Bladnodene er 17, 60, 4, 11 og 45. De har ingen underordnede noder. Det er derfor de er bladnoder. Så vi starter heapify-metoden fra deres overordnede node. Her er trinnene:

Trinn 1) Velg undertreet lengst til venstre. Hvis undernodene er større, bytt den overordnede noden med den underordnede noden.

Her er foreldrenoden 9. Og undernodene er 17 og 60. Ettersom 60 er den største, vil 60 og 9 bli byttet for å opprettholde maks haug.

Trinn 2) Nå er undertreet lengst til venstre heapified. Den neste overordnede noden er 7. Denne forelderen har to underordnede noder, og den største er 45. Så 45 og 7 vil bli byttet.

Trinn 3) Nodene 60 og 4 har overordnet node 5. Ettersom "5" er mindre enn den underordnede noden 60, vil den bli byttet.

Trinn 4) Nå har node 5 den underordnede noden 17,9. Dette opprettholder ikke egenskapen for maksimal haug. Så 5 vil bli erstattet med 17.

Trinn 5) Node 10 vil bli byttet med 60, deretter byttet med 17. Prosessen vil se slik ut.

Trinn 6) Frem til trinn 5 opprettet vi den maksimale haugen. Hver overordnet node er større enn dens underordnede noder. Rotnoden har maksimumsverdien (60).

OBS: For å lage den sorterte matrisen, må vi erstatte den maksimalt verdsatte noden med dens etterfølger.

Denne prosessen kalles "ekstrakt maks". Siden 60 er maks-noden, vil vi fikse posisjonen til den 0. indeksen og lage haugen uten node 60.

Trinn 7) Ettersom 60 er fjernet, er neste maksimalverdi 45. Vi vil gjøre prosessen "Extract Max" igjen fra node 45.

Denne gangen får vi 45 og erstatter rotnoden med etterfølgeren 17.

Vi må prestere"Uttrekk Maks” til alle elementene er sortert.

Etter å ha gjort disse trinnene til vi trekker ut alle maksverdiene, får vi følgende array.

Hva er Binary Heap?

En binær haug er en slags komplett binært tre datastruktur. I denne typen trestruktur er overordnet node enten større eller mindre enn undernodene. Hvis foreldrenoden er mindre, kalles haugen "Min Heap", og hvis foreldrenoden er større, kalles haugen "Max Heap".

Her er eksempler på min haug og maks haug.

I figuren ovenfor, hvis du legger merke til "Min Heap", er den overordnede noden alltid mindre enn dens underordnede noder. På toppen av treet kan vi finne den minste verdien 10.

På samme måte, for "Max Heap", er overordnet node alltid større enn undernodene. Det maksimale elementet er tilstede ved hodenoden for "Max Heap".

Hva er "Heapify"?

"Heapify" er prinsippet for heapen som sikrer posisjonen til noden. I Heapify opprettholder en maks haug alltid et forhold til foreldre og barn, og det vil si at overordnet node vil være større enn undernodene.

For eksempel, hvis en ny node legges til, må vi omforme haugen. Imidlertid må vi kanskje endre eller bytte noder eller omorganisere array. Denne prosessen med å omforme en haug kalles "heapify".

Her er et eksempel på hvordan heapify fungerer:

Legge til en ny node og Heapify — Legger til en ny node og heapify

Her er trinnene for heapify:

Trinn 1) Lagt til node 65 som høyre underordnet av node 60.

Trinn 2) Sjekk om den nylig lagt til noden er større enn den overordnede.

Trinn 3) Siden den er større enn foreldrenoden, byttet vi det riktige barnet med dets overordnede.

Hvordan bygge haugen

Før vi bygger haugen eller heapify et tre, må vi vite hvordan vi skal lagre den. Siden haugen er et komplett binært tre, er det bedre å bruke en matrise å holde dataene til haugen.

La oss si at en matrise inneholder totalt n elementer. Hvis "i" indeks er en overordnet node, vil venstre node være på indeks (2i+1), og den høyre noden vil være ved indeks (2i+2). Vi antar at array-indeksen begynner fra 0.

Ved å bruke dette, la oss lagre en maks haug til en array-lignende følgende:

Array-basert representasjon av Max Heap — Array-basert representasjon av den maksimale heapen

Heapify-algoritmen opprettholder heap-egenskapen. Hvis forelderen ikke har ekstremverdien (mindre eller større), vil den bli byttet med den mest ekstreme barnenoden.

Her er trinnene for å heapify en maks haug:

Trinn 1) Start fra bladnoden.

Trinn 2) Finn maksimum mellom foreldre og barn.

Trinn 3) Bytt nodene hvis den underordnede noden har en større verdi enn den overordnede.

Trinn 4) Gå ett nivå opp.

Trinn 5) Følg trinn 2,3,4 til vi når indeks 0 eller sorter hele treet.

Her er pseudokoden for rekursiv heapify (maks 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)

Pseudokode for haugsortering

Her er pseudokoden for 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)

Eksempel på haugsorteringskode i 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);
}

Utgang:

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

Eksempel på haugsorteringskode i 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)

Utgang:

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

Tid og rom kompleksitetsanalyse av Heap Sort

Det er tidskompleksitet og romkompleksitet som vi kan analysere for haugsorten. For tidskompleksitet har vi følgende tilfeller:

Beste sak
Gjennomsnittlig sak
Verste tilfelle

Heapen er implementert på et komplett binært tre. Så, på bunnnivået av det binære treet, vil det være maksimalt antall noder. Hvis det nederste nivået har n noder, vil nivået ovenfor ha n/2 noder.

I dette eksemplet har nivå 3 fire elementer, nivå 2 har to elementer, og nivå 1 har ett element. Hvis det er totalt n antall elementer, vil høyden eller totalnivået være Logg₂(n). Så å sette inn et enkelt element kan ta maksimalt Log(n) iterasjoner.

Når vi vil ta maksimalverdien fra haugen, tar vi bare rotnoden. Så igjen, kjør heapify. Hver heapify tar Logg₂(N) tid. Å trekke ut maksimumet tar O(1) tid.

Best case-tidskompleksitet for heap-sorteringsalgoritme

Når alle elementene allerede er sortert i matrisen, vil det ta O(n) tid å bygge haugen. Fordi hvis listen er sortert, vil det å sette inn et element ta den konstante tiden som er O(1).

Så det vil ta O(n) tid å lage en max-heap eller min-heap i beste fall.

Gjennomsnittlig sakstidskompleksitet for haugsorteringsalgoritme

Å sette inn en vare eller trekke ut en maksimal koster O(log(n)) tid. Så den gjennomsnittlige sakstidskompleksiteten for heap-sorteringsalgoritmen er O(n log(n)).

Worst Case Time Complexity for Heap Sort Algorithm

I likhet med gjennomsnittlig tilfelle, i verste fall, kan vi utføre heapify n ganger. Hver heapify vil koste O(log(n)) tid. Så, den verste tid kompleksiteten vil være O(n log(n)).

Space Complexity for Heap Sort Algorithm

Heap sort er en algoritme som er designet på stedet. Dette betyr at det ikke trengs noe ekstra eller midlertidig minne for å utføre oppgaven. Hvis vi ser implementeringen, vil vi legge merke til at vi brukte swap () for å utføre utvekslingen av nodene. Ingen annen liste eller matrise var nødvendig. Så romkompleksiteten er O(1).