Algoritam za sortiranje hrpe (s kodom u Python i C++)

Što je algoritam Heap Sort?

Heap Sort je jedan od popularnih i bržih algoritama za sortiranje. Izgrađen je na cjelovitoj strukturi podataka binarnog stabla. Potražit ćemo maksimalni element i staviti ga na vrh za maksimalnu hrpu. Stavit ćemo ga na roditeljski čvor binarnog stabla.

Recimo da je dan niz, podaci = [10,5, 7, 9, 4, 11, 45, 17, 60].

U nizu, ako je i-ti (i=0,1,2,3 …) indeks nadređeni čvor tada će (2i+1) i (2i+2) biti lijevi i desni potomci. Stvaranje potpunog binarnog stabla s ovim nizom izgledat će ovako:

Napravit ćemo heapify proces od početka do kraja niza. U početku, ako pretvorimo niz u stablo, izgledat će kao gore. Vidimo da ne održava nikakvo svojstvo hrpe (min-hop ili maksimalna hrpa). Dobit ćemo razvrstani niz izvođenjem heapify procesa za sve čvorove.

Primjena Heap sortiranja

Evo neke upotrebe algoritma za sortiranje hrpe:

Konstrukcija "prioritetnih redova" zahtijeva sortiranje hrpe. Budući da heapsort održava element sortiranim nakon svakog umetanja.
Heap Data Structure učinkovita je u pronalaženju k^th najveći element u datom nizu.
Linux kernel koristi heap sortiranje kao zadano algoritam sortiranja budući da ima O (1) prostornu složenost.

Stvorite Heap sortiranje s primjerom

Ovdje ćemo konstruirati max heap iz sljedećeg kompletnog binarnog stabla.

Čvorovi lista su 17, 60, 4, 11 i 45. Nemaju čvorove potomke. Zato su lisni čvorovi. Dakle, pokrenut ćemo heapify metodu iz njihovog nadređenog čvora. Evo koraka:

Korak 1) Odaberite krajnje lijevo podstablo. Ako su podređeni čvorovi veći, zamijenite roditeljski čvor s podređenim čvorom.

Ovdje je roditeljski čvor 9. A podređeni čvorovi su 17 i 60. Budući da je 60 najveći, 60 i 9 će se zamijeniti kako bi se održao max gomila.

Korak 2) Sada je krajnje lijevo podstablo gomilano. Sljedeći nadređeni čvor je 7. Ovaj roditelj ima dva podređena čvora, a najveći je 45. Dakle, 45 i 7 će biti zamijenjeni.

Korak 3) Čvorovi 60 i 4 imaju nadređeni čvor 5. Kako je "5" manji od podređenog čvora 60, bit će zamijenjen.

Korak 4) Sada, čvor 5 ima podređeni čvor 17,9. Ovo ne održava svojstvo maksimalne hrpe. Dakle, 5 će biti zamijenjeno sa 17.

Korak 5) Čvor 10 bit će zamijenjen s 60, zatim s 17. Proces će izgledati ovako.

Korak 6) Do koraka 5 stvorili smo maksimalnu hrpu. Svaki nadređeni čvor je veći od svojih podređenih čvorova. Korijenski čvor ima najveću vrijednost (60).

Bilješka: Da bismo stvorili sortirani niz, trebamo zamijeniti čvor s maksimalnom vrijednošću njegovim nasljednikom.

Ovaj proces se naziva "ekstrakt max”. Kako je 60 maksimalni čvor, fiksirati ćemo njegovu poziciju na 0. indeks i kreirati gomilu bez čvora 60.

Korak 7) Kako se 60 ukloni, sljedeća maksimalna vrijednost je 45. Iz čvora 45 ponovno ćemo izvršiti proces "Izdvoj maks.".

Ovaj put ćemo dobiti 45 i zamijeniti korijenski čvor s njegovim nasljednikom 17.

Moramo izvesti"Ekstrakt Maks” dok se svi elementi ne poslože.

Nakon izvođenja ovih koraka dok ne izdvojimo sve maksimalne vrijednosti, dobit ćemo sljedeći niz.

Što je binarna gomila?

Binarna gomila je neka vrsta potpune binarno stablo struktura podataka. U ovoj vrsti strukture stabla, nadređeni čvor je veći ili manji od podređenih čvorova. Ako je nadređeni čvor manji, hrpa se naziva "Minimalna hrpa", a ako je nadređeni čvor veći, hrpa se naziva "Maksimalna hrpa".

Evo primjera minimalne hrpe i maksimalne hrpe.

Na gornjoj slici, ako primijetite "Min Heap", nadređeni čvor uvijek je manji od svojih podređenih čvorova. Na čelu stabla možemo pronaći najmanju vrijednost 10.

Slično, za "Max Heap", nadređeni čvor uvijek je veći od podređenih čvorova. Maksimalni element prisutan je u glavnom čvoru za "Max Heap".

Što je “Heapify”?

“Heapify” je princip gomile koji osigurava poziciju čvora. U Heapifyju maksimalna gomila uvijek održava odnos s roditeljem i dijetetom, a to je da će roditeljski čvor biti veći od podređenih čvorova.

Na primjer, ako se doda novi čvor, trebamo preoblikovati hrpu. Međutim, možda ćemo trebati promijeniti ili zamijeniti čvorove ili preurediti niz. Ovaj proces preoblikovanja gomile naziva se "heapify".

Evo primjera kako heapify funkcionira:

Dodavanje novog čvora i Heapify — Dodavanje novog čvora i heapifyja

Evo koraka za heapify:

Korak 1) Dodan je čvor 65 kao desni potomak čvora 60.

Korak 2) Provjerite je li novododani čvor veći od nadređenog.

Korak 3) Budući da je veći od roditeljskog čvora, zamijenili smo pravo dijete s njegovim roditeljem.

Kako izgraditi Heap

Prije izgradnje gomile ili gomilanja stabla, moramo znati kako ćemo ga skladištiti. Kako je gomila potpuno binarno stablo, bolje je koristiti an poredak za držanje podataka hrpe.

Recimo da niz sadrži ukupno n elemenata. Ako je “i” indeks nadređeni čvor, onda će lijevi čvor biti na indeksu (2i+1), a desni čvor će biti na indeksu (2i+2). Pretpostavljamo da indeks niza počinje od 0.

Koristeći ovo, pohranimo maksimalnu hrpu u niz nalik sljedećem:

Predstavljanje maksimalne hrpe temeljeno na nizu — Predstavljanje maksimalne gomile temeljeno na nizu

Heapify algoritam održava heap svojstvo. Ako roditelj nema ekstremnu vrijednost (manju ili veću), zamijenit će se s najekstremnijim podređenim čvorom.

Evo koraka za gomilanje maksimalne gomile:

Korak 1) Počnite od čvora lista.

Korak 2) Pronađite maksimum između roditelja i djece.

Korak 3) Zamijenite čvorove ako podređeni čvor ima veću vrijednost od nadređenog.

Korak 4) Idi jednu razinu više.

Korak 5) Slijedite korake 2,3,4 dok ne dođemo do indeksa 0 ili sortiramo cijelo stablo.

Evo pseudokoda za rekurzivnu 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 kod za Heap sortiranje

Evo pseudokoda za algoritam za sortiranje hrpe:

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)

Primjer Heap Sort 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);
}

Izlaz:

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

Primjer Heap Sort 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)

Izlaz:

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

Vremenska i prostorna analiza složenosti Heap sortiranja

Postoji vremenska složenost i prostorna složenost koje možemo analizirati za sortiranje hrpe. Za vremensku složenost imamo sljedeće slučajeve:

Najbolji slučaj
Prosječan slučaj
Najgori slučaj

Hrpa je implementirana na potpunom binarnom stablu. Dakle, na donjoj razini binarnog stabla bit će najveći broj čvorova. Ako donja razina ima n čvorova, tada će gornja razina imati n/2 čvora.

U ovom primjeru, razina 3 ima četiri stavke, razina 2 ima dvije stavke, a razina 1 ima jednu stavku. Ako postoji ukupan broj stavki n, bit će visina ili ukupna razina Dnevnik₂(n). Dakle, umetanje jednog elementa može trajati najviše Log(n) ponavljanja.

Kada želimo uzeti maksimalnu vrijednost iz hrpe, uzimamo samo korijenski čvor. Zatim opet pokrenite heapify. Svaki heapify uzima Dnevnik₂(N) vrijeme. Izdvajanje maksimuma traje O(1) vremena.

Najbolji slučaj vremenske složenosti za algoritam Heap sortiranja

Kada su svi elementi već sortirani u nizu, bit će potrebno O(n) vremena da se izgradi hrpa. Jer ako je popis sortiran tada će umetanje stavke trajati konstantno vrijeme koje je O(1).

Dakle, trebat će O(n) vremena da se stvori max-heap ili min-heap u najboljem slučaju.

Prosječna složenost slučaja za algoritam sortiranja hrpe

Umetanje stavke ili izdvajanje maksimuma košta O(log(n)) vremena. Dakle, prosječna složenost slučaja za algoritam sortiranja hrpe je O(n log(n)).

Vremenska složenost u najgorem slučaju za algoritam sortiranja hrpe

Slično prosječnom slučaju, u najgorem slučaju, mogli bismo izvršiti heapify n puta. Svako heapify će koštati O(log(n)) vremena. Dakle, vremenska složenost u najgorem slučaju bit će O(n log(n)).

Složenost prostora za algoritam sortiranja gomile

Heap sortiranje je algoritam dizajniran na mjestu. To znači da za izvođenje zadatka nije potrebna dodatna ili privremena memorija. Ako vidimo implementaciju, primijetit ćemo da smo koristili swap () za izvođenje razmjene čvorova. Nikakav drugi popis ili niz nije bio potreban. Dakle, kompleksnost prostora je O(1).

Možda ti se svidi: