Kuhjade sortimise algoritm (koos koodiga Python ja C++)
Sarah Chen
Mis on kuhjade sortimise algoritm?
Heap Sort on üks populaarsemaid ja kiiremaid sortimisalgoritme. See on üles ehitatud täielikule binaarpuu andmestruktuurile. Otsime maksimaalse elemendi ja paneme selle maksimaalse hunniku ülaossa. Asetame selle kahendpuu emasõlmele.
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 leidmiselth 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 "ekstrakt max”. Kuna 60 on maksimaalne sõlm, fikseerime selle asukoha 0. indeksiga ja loome hunniku ilma sõlmeta 60.
Step 7) Kuna 60 eemaldatakse, on järgmine maksimumväärtus 45. Teeme sõlmest 45 uuesti protsessi “Extract Max”.
Seekord saame 45 ja asendame juursõlme selle järglasega 17.
Peame esinema "Väljavõte Max” kuni kõik elemendid on sorteeritud.
Pärast nende toimingute tegemist, kuni ekstraheerime kõik maksimaalsed väärtused, 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 juhtuda, et peame sõlmesid muutma või vahetama või massiivi ümber korraldama. Seda kuhja ümberkujundamise protsessi 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)
Kuhjade sortimise pseudokood
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)
Kuhja sortimise koodi näide 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
Kuhja sortimise koodi näide 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:
- Parim juhtum
- Keskmine juhtum
- 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 Logi2(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 Logi2(n) aega. Maksimumi eraldamine 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
Kauba sisestamine või maksimaalse väljavõte maksab O(log(n)) aega. Seega on kuhja sortimise algoritmi juhtumite keskmine 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).
