Keon lajittelualgoritmi (kanssa Code in Python ja C++)

Mikä on Keon lajittelualgoritmi?

Kekolajittelu on yksi suosituimmista ja nopeimmista lajittelualgoritmeista. Se perustuu täydelliseen binääripuun tietorakenteeseen. Etsimme suurimman mahdollisen elementin ja sijoitamme sen suurimman mahdollisen keon päälle. Sijoitamme sen binääripuun ylä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 "extract-maksimi”. 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. Suoritamme prosessin ”Esimerkkitract Max” uudelleen solmusta 45.

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

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

Näiden vaiheiden jälkeen, kunnes olemmetrackaikki 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.

Esimerkiksi jos lisätään uusi solmu, meidän on muotoiltava keko uudelleen. Saatamme kuitenkin joutua muuttamaan tai vaihtamaan solmuja tai järjestelemään taulukon uudelleen. Tämä uudelleenjärjestämisprosessiping Kekoa kutsutaan "kekoksi".

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

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:

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)

Pseudo Code keon lajittelua varten

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 kekolajittelusta 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);
}

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 kekolajittelusta 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)

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:

1. Paras tapaus
2. Keskimääräinen kotelo
3. 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. Esim.tracMaksimin saavuttaminen vie 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 tai esimerkin lisääminentracMaksimin asettaminen maksaa O(log(n)) aikaa. Joten kekolajittelualgoritmin keskimääräinen tapauskohtainen aikakompleksisuus 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).

UKK