Keon lajittelualgoritmi (koodi sisään Python ja C++)

Mikä on Keon lajittelualgoritmi?

Heap Sort on yksi suosituimmista ja nopeammista lajittelualgoritmeista. Se perustuu täydelliseen binääripuutietorakenteeseen. Etsimme maksimielementin ja laitamme sen yläosaan maksimikasaa varten. Laitamme sen binääripuun pääsolmuun.

Oletetaan, että matriisi on annettu, data = [10,5, 7, 9, 4, 11, 45, 17, 60].

Jos taulukossa i-th (i=0,1,2,3 …) indeksi on pääsolmu, (2i+1) ja (2i+2) ovat vasen ja oikea lapsi. Täydellisen binääripuun luominen tällä taulukolla näyttää tältä:

Teemme kasaanmuodostusprosessin taulukon alusta loppuun. Aluksi, jos muunnamme taulukon puuksi, se näyttää yllä olevalta. Voimme nähdä, että se ei ylläpidä mitään keon ominaisuutta (min-heap tai max kaso). Saadaan lajiteltu matriisi tekemällä kasatusprosessi kaikille solmuille.

Kekon lajittelun sovellus

Tässä on keon lajittelualgoritmin käyttöä:

"Priority Queues" -jonojen rakentaminen vaatii kasalajittelun. Koska heapsort pitää elementin lajiteltuna jokaisen lisäyksen jälkeen.
Keon tietorakenne on tehokas k:n löytämisessä^th suurin elementti tietyssä taulukossa.
Linux-ydin käyttää keon lajittelua oletuksena lajittelualgoritmi koska sillä on O (1) avaruuden monimutkaisuus.

Luo Kekolajittelu esimerkin avulla

Tässä rakennamme maksimikeon seuraavasta täydellisestä binääripuusta.

Lehtisolmut ovat 17, 60, 4, 11 ja 45. Niillä ei ole lapsisolmuja. Siksi ne ovat lehtisolmuja. Joten aloitamme kasaantumismenetelmän heidän yläsolmuksestaan. Tässä ovat vaiheet:

Vaihe 1) Valitse vasemmanpuoleisin alipuu. Jos alisolmut ovat suurempia, vaihda pääsolmu alisolmun kanssa.

Tässä yläsolmu on 9. Ja alasolmut ovat 17 ja 60. Koska 60 on suurin, 60 ja 9 vaihdetaan keskenään ylläpitämään max kasa.

Vaihe 2) Nyt vasemmanpuoleisin alipuu on kasattu. Seuraava pääsolmu on 7. Tällä pääsolmulla on kaksi alisolmua, ja suurin on 45. Joten 45 ja 7 vaihdetaan.

Vaihe 3) Solmuilla 60 ja 4 on yläsolmu 5. Koska "5" on pienempi kuin alisolmu 60, se vaihdetaan.

Vaihe 4) Nyt solmulla 5 on lapsisolmu 17,9. Tämä ei ylläpidä maksimikeon ominaisuutta. Joten 5 korvataan 17:llä.

Vaihe 5) Solmu 10 vaihdetaan 60:een ja sitten 17:ään. Prosessi näyttää seuraavalta.

Vaihe 6) Vaiheeseen 5 saakka loimme maksimikeon. Jokainen yläsolmu on suurempi kuin sen alisolmu. Juurisolmulla on suurin arvo (60).

Huomautus: Lajitellun taulukon luomiseksi meidän on korvattava maksimiarvoinen solmu sen seuraajalla.

Tätä prosessia kutsutaan "poimi max”. Koska 60 on maksimisolmu, kiinnitämme sen sijainnin 0. indeksiin ja luomme kasan ilman solmua 60.

Vaihe 7) Kun 60 poistetaan, seuraava maksimiarvo on 45. Teemme prosessin "Extract Max" uudelleen solmusta 45.

Tällä kertaa saamme 45 ja korvaamme juurisolmun sen seuraajalla 17.

Meidän on suoritettava "Ote Max", kunnes kaikki elementit on lajiteltu.

Kun olet tehnyt nämä vaiheet, kunnes puramme kaikki maksimiarvot, saamme seuraavan taulukon.

Mikä on Binary Heap?

Binary Heap on eräänlainen täydellinen binaaripuu tietorakenne. Tällaisessa puurakenteessa pääsolmu on joko suurempi tai pienempi kuin lapsisolmut. Jos yläsolmu on pienempi, niin kasaa kutsutaan "Minimikekoksi" ja jos emosolmu on suurempi, kasaa kutsutaan "Max Heap".

Tässä on esimerkkejä minimikeosta ja maksimikeosta.

Jos yllä olevassa kuvassa huomaat "Min Heap", pääsolmu on aina pienempi kuin sen alisolmut. Puun kärjestä löytyy pienin arvo 10.

Samoin "Max Heap" -kohdassa yläsolmu on aina suurempi kuin alisolmut. Maksimielementti on "Max Heap" -pääsolmussa.

Mikä on "Heapify"?

"Heapify" on kasan periaate, joka varmistaa solmun sijainnin. Heapifyssa maksimikeko ylläpitää aina suhdetta vanhemman ja lapsen kanssa, mikä tarkoittaa, että yläsolmu on suurempi kuin alisolmut.

Jos esimerkiksi lisätään uusi solmu, meidän on muotoiltava kasa uudelleen. Meidän on kuitenkin ehkä muutettava tai vaihdettava solmuja tai järjestettävä taulukko uudelleen. Tätä kasan uudelleenmuotoiluprosessia kutsutaan "kasaamiseksi".

Tässä on esimerkki siitä, kuinka heapify toimii:

Uuden solmun lisääminen ja Heapify — Uuden solmun lisääminen ja kasaaminen

Tässä ovat kasaamisen vaiheet:

Vaihe 1) Lisätty solmu 65 solmun 60 oikeaksi lapseksi.

Vaihe 2) Tarkista, onko juuri lisätty solmu suurempi kuin pääsolmu.

Vaihe 3) Koska se on suurempi kuin emosolmu, vaihdoimme oikean lapsen sen ylätason kanssa.

Kuinka rakentaa kasa

Ennen kuin rakennat kasan tai kasaamme puun, meidän on tiedettävä, kuinka säilytämme sen. Koska kasa on täydellinen binääripuu, on parempi käyttää a ryhmä kasan tietojen säilyttämiseen.

Oletetaan, että taulukko sisältää yhteensä n elementtiä. Jos "i":s indeksi on yläsolmu, vasen solmu on indeksissä (2i+1), ja oikea solmu on indeksissä (2i+2). Oletetaan, että taulukkoindeksi alkaa 0:sta.

Tallennetaan tätä käyttämällä maksimikeko taulukon kaltaiseen seuraavaan:

Suurin kasan taulukkopohjainen esitys — Enimmäiskeon taulukkopohjainen esitys

Keonmuodostusalgoritmi ylläpitää keon ominaisuutta. Jos vanhemmalla ei ole ääriarvoa (pienempi tai suurempi), se vaihdetaan äärimmäisimmän lapsisolmun kanssa.

Tässä ovat vaiheet maksimikasan kasoittamiseksi:

Vaihe 1) Aloita lehden solmusta.

Vaihe 2) Etsi maksimi vanhemman ja lasten välillä.

Vaihe 3) Vaihda solmut, jos alisolmun arvo on suurempi kuin pääsolmun arvo.

Vaihe 4) Mene yksi taso ylöspäin.

Vaihe 5) Noudata vaiheita 2,3,4, kunnes saavutamme indeksin 0 tai lajittelemme koko puun.

Tässä on pseudokoodi rekursiiviselle kasalle (maksimi kasa):

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)

Pseudokoodi keon lajittelulle

Tässä on pseudokoodi keon lajittelualgoritmille:

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)

Esimerkki keon lajittelukoodista 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);
}

lähtö:

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

Esimerkki keon lajittelukoodista 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)

lähtö:

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

Keon lajittelun aika ja tila monimutkaisuusanalyysi

Voimme analysoida keon lajittelua varten aika- ja tilamonimutkaisuutta. Ajan monimutkaisuuden vuoksi meillä on seuraavat tapaukset:

Paras tapaus
Keskimääräinen kotelo
Pahimmassa tapauksessa

Keko toteutetaan täydellisessä binääripuussa. Joten binääripuun alimmalla tasolla on suurin määrä solmuja. Jos alimmalla tasolla on n solmua, niin yllä olevalla tasolla on n/2 solmua.

Tässä esimerkissä tasolla 3 on neljä kohdetta, tasolla 2 on kaksi kohdetta ja tasolla 1 on yksi kohde. Jos kohteita on yhteensä n, korkeus tai kokonaistaso on Kirjaudu₂(n). Joten yhden elementin lisääminen voi kestää enintään Log(n) iteraatioita.

Kun haluamme ottaa kasan maksimiarvon, otamme vain juurisolmun. Suorita sitten taas heapify. Jokainen kasapaino kestää Kirjaudu₂(N) aika. Maksimiarvon poistaminen kestää O(1) aikaa.

Paras tapaus-ajan monimutkaisuus keon lajittelualgoritmille

Kun kaikki elementit on jo lajiteltu taulukossa, keon rakentaminen kestää O(n) aikaa. Koska jos luettelo on lajiteltu, kohteen lisääminen vie vakioajan, joka on O(1).

Eli max-keon tai min-keon luominen kestää parhaassa tapauksessa O(n) aikaa.

Keskimääräinen tapausajan monimutkaisuus keon lajittelualgoritmille

Kohteen lisääminen tai enimmäismäärän purkaminen maksaa O(log(n))-aikaa. Joten keon lajittelualgoritmin tapauksen keskimääräinen aika monimutkaisuus on O(n log(n)).

Huonoin tapauksen aika monimutkaisuus keon lajittelualgoritmille

Keskimääräisen tapauksen tapaan, pahimmassa tapauksessa saatamme tehdä kasaan n kertaa. Jokainen pinoaminen maksaa O(log(n)) aikaa. Joten, pahimman tapauksen aika monimutkaisuus on O(n log(n)).

Tilan monimutkaisuus keon lajittelualgoritmille

Keon lajittelu on paikallaan suunniteltu algoritmi. Tämä tarkoittaa, että tehtävän suorittamiseen ei tarvita ylimääräistä tai väliaikaista muistia. Jos näemme toteutuksen, huomaamme, että käytimme vaihtoa () solmujen vaihdon suorittamiseen. Muuta listaa tai taulukkoa ei tarvittu. Joten avaruuden kompleksisuus on O(1).