Hunniku sortimise algoritm (koos Code in Python ja C++)

Mis on kuhjade sortimise algoritm?

Kuhjasortimine on üks populaarsemaid ja kiiremaid sortimisalgoritme. See põhineb täielikul binaarpuu andmestruktuuril. Otsime maksimaalse elemendi ja asetame selle maksimaalse kuhja saamiseks tippu. Asetame selle binaarpuu ülemsõlme.

Oletame, et massiiv on antud, andmed = [10,5, 7, 9, 4, 11, 45, 17, 60].

Kui massiivi i-s (i=0,1,2,3 …) indeks on emasõlm, on (2i+1) ja (2i+2) vasak ja parem alamsõlm. Täieliku binaarpuu loomine selle massiiviga näeb välja järgmine:

Teeme kuhjastamise protsessi massiivi algusest lõpuni. Esialgu, kui teisendame massiivi puuks, näeb see välja nagu ülaltoodud. Näeme, et see ei säilita ühtegi hunniku omadust (min-heap või max hunnik). Sorteeritud massiivi saame kõigi sõlmede jaoks kuhjade moodustamise protsessiga.

Kuhjade sortimise rakendamine

Siin on mõned kuhja sortimise algoritmi kasutusviisid:

• Prioriteetsete järjekordade loomine vajab hunniku sortimist. Kuna hepsort hoiab elemendi sorteerituna pärast iga sisestamist.
• Kuhja andmestruktuur on tõhus k leidmisel^th antud massiivi suurim element.
• Linuxi kernel kasutab vaikimisi hunniku sortimist sortimisalgoritm kuna sellel on O (1) ruumi keerukus.

Looge näite abil kuhjade sortimine

Siin koostame järgmisest täielikust kahendpuust maksimaalse hunniku.

Lehesõlmed on 17, 60, 4, 11 ja 45. Neil pole alamsõlme. Sellepärast on nad lehtede sõlmed. Niisiis, alustame kuhjastamise meetodit nende emasõlmest. Siin on sammud.

Step 1) Valige vasakpoolseim alampuu. Kui alamsõlmed on suuremad, vahetage vanemsõlm alamsõlmega.

Siin on emasõlm 9. Ja alamsõlmed on 17 ja 60. Kuna 60 on suurim, vahetatakse 60 ja 9, et säilitada max kuhjaga.

Step 2) Nüüd on kõige vasakpoolsem alampuu kuhjatud. Järgmine ülemsõlm on 7. Sellel vanemal on kaks alamsõlme ja suurim on 45. Seega vahetatakse 45 ja 7.

Step 3) Sõlmedel 60 ja 4 on emasõlm 5. Kuna "5" on väiksem kui alamsõlm 60, siis see vahetatakse.

Step 4) Nüüd on sõlmel 5 alamsõlm 17,9. See ei ole maksimaalse kuhja omaduse säilitamine. Niisiis, 5 asendatakse 17-ga.

Step 5) Sõlm 10 asendatakse 60-ga ja seejärel 17-ga. Protsess näeb välja järgmine.

Step 6) Kuni 5. sammuni lõime maksimaalse hunniku. Iga vanemsõlm on suurem kui tema alamsõlmed. Juursõlmel on maksimaalne väärtus (60).

Märge: Sorteeritud massiivi loomiseks peame asendama maksimaalse väärtusega sõlme selle järglasega.

Seda protsessi nimetatakse "extract-maks”. Kuna 60 on maksimaalne sõlm, fikseerime selle asukoha 0. indeksiga ja loome hunniku ilma sõlmeta 60.

Step 7) Kui 60 on eemaldatud, on järgmine maksimaalne väärtus 45. Teeme protsessi „Näidetrac„t Max” uuesti sõlmest 45.

Seekord saame 45 ja asendame juursõlme selle järglasega 17.

Peame esinema "Extract Max” kuni kõik elemendid on sorteeritud.

Pärast nende sammude tegemist kuni me extracKõikide maksimaalsete väärtuste korral saame järgmise massiivi.

Mis on binaarne hunnik?

Binary Heap on omamoodi täielik binaarne puu andmete struktuur. Sellises puustruktuuris on põhisõlm alamsõlmedest suurem või väiksem. Kui emasõlm on väiksem, nimetatakse kuhja "Min Heap" ja kui vanem sõlm on suurem, nimetatakse hunnikut "Max Heap".

Siin on näited minimaalsest ja maksimaalsest kuhjast.

Kui märkate ülaloleval joonisel "Min Heap", on emasõlm alati väiksem kui selle alamsõlmed. Puu otsast leiame väikseima väärtuse 10.

Samamoodi on „Max Heap” puhul emasõlm alati suurem kui alamsõlmed. Maksimaalne element on "Max Heap" peasõlmes.

Mis on "Heapify"?

“Heapify” on kuhja põhimõte, mis tagab sõlme asukoha. Heapifys säilitab maksimaalne hunnik alati suhte vanema ja lapsega ning see tähendab, et vanemsõlm on suurem kui alamsõlmed.

Näiteks kui lisatakse uus sõlm, peame kuhja ümber kujundama. Siiski võib meil olla vaja sõlmi muuta või vahetada või massiivi ümber korraldada. See ümberkujundamise protsessping Kuhja nimetatakse "kuhjamiseks".

Siin on näide kuhjamise toimimisest:

Siin on kuhjamise toimingud:

Step 1) Lisati sõlm 65 kui sõlme 60 parem alam.

Step 2) Kontrollige, kas äsja lisatud sõlm on suurem kui ülem.

Step 3) Kuna see on ülemsõlmest suurem, vahetasime õige alamsõlme vanemaga.

Kuidas hunnikut ehitada

Enne hunniku ehitamist või puu kuhjamist peame teadma, kuidas me seda ladustame. Kuna hunnik on täielik kahendpuu, on parem kasutada an massiivi kuhja andmete hoidmiseks.

Oletame, et massiiv sisaldab kokku n elementi. Kui "i" indeks on emasõlm, on vasak sõlm indeksis (2i+1), ja parem sõlm on indeksis (2i+2). Eeldame, et massiivi indeks algab 0-st.

Kasutades seda, salvestame maksimaalse hunniku järgmise massiivi sarnasesse kohta:

Kuhjade loomise algoritm säilitab kuhja omaduse. Kui vanemal ei ole äärmist väärtust (väiksem või suurem), vahetatakse see kõige äärmuslikuma alamsõlmega.

Siin on juhised maksimaalse hunniku kuhjamiseks.

Step 1) Alusta lehesõlmest.

Step 2) Leia maksimum vanema ja laste vahel.

Step 3) Vahetage sõlmed, kui alamsõlme väärtus on suurem kui vanemsõlmel.

Step 4) Mine ühe taseme võrra kõrgemale.

Step 5) Järgige samme 2,3,4, 0, XNUMX, kuni jõuame indeksini XNUMX või sorteerime kogu puu.

Siin on pseudokood rekursiivse hunniku jaoks (maksimaalne kuhja):

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 Heap Sort jaoks

Siin on hunniku sortimise algoritmi pseudokood:

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)

Näide kuhjasortimisest 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);
}

Väljund:

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

Näide kuhjasortimisest 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)

Väljund:

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

Kuhjade sortimise aja ja ruumi keerukuse analüüs

Aja keerukust ja ruumi keerukust saame analüüsida hunniku sortimiseks. Ajalise keerukuse huvides on meil järgmised juhtumid:

1. Parim juhtum
2. Keskmine juhtum
3. Halvimal juhul

Kuhja rakendatakse täielikul kahendpuul. Seega on binaarpuu alumisel tasemel maksimaalne sõlmede arv. Kui alumisel tasemel on n sõlme, siis ülaloleval tasemel on n/2 sõlme.

Selles näites on 3. tasemel neli üksust, 2. tasemel kaks ja 1. tasemel üks üksus. Kui objekte on kokku n, on kõrgus või kogutase Logi₂(n). Seega võib ühe elemendi sisestamine võtta maksimaalselt Log(n) iteratsiooni.

Kui tahame kuhjast võtta maksimaalse väärtuse, võtame lihtsalt juursõlme. Seejärel taaskäivitage heapify. Iga hunnik võtab Logi₂(n) aeg. NäidetracMaksimumi leidmine võtab aega O(1).

Kuhjade sortimise algoritmi parim juhtumi aja keerukus

Kui kõik elemendid on massiivi juba sorteeritud, kulub kuhja loomiseks O(n) aega. Sest kui loend on sorteeritud, võtab üksuse sisestamine konstantse aja, mis on O(1).

Nii et parimal juhul kulub max- või min-hunniku loomiseks O(n) aega.

Kuhjade sortimise algoritmi keskmine juhtumi aja keerukus

Elemendi või elemendi sisestaminetracMaksimaalse juhtumi leidmine maksab O(log(n)) aega. Seega on kuhjasortimise algoritmi keskmine juhtumi aja keerukus O(n log(n)).

Kuhjade sortimise algoritmi halvimal juhul keerukus

Sarnaselt keskmisele juhtumile võime halvima stsenaariumi korral esineda n korda. Iga hunnik maksab O(log(n)) aega. Seega on ajaline keerukus halvimal juhul O(n log(n)).

Ruumi keerukus kuhjade sortimise algoritmi jaoks

Kuhja sortimine on kohapeal loodud algoritm. See tähendab, et ülesande täitmiseks pole vaja lisamälu ega ajutist mälu. Kui näeme teostust, märkame, et kasutasime sõlmede vahetamiseks vahetust (). Muud loendit või massiivi polnud vaja. Seega on ruumi keerukus O(1).

KKK