Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

pino

Kasa ja prioriteettijono:

Prioriteettijono on abstrakti tietotyyppi, ja kasa on tietorakenne, joten kasa ei ole prioriteettijono.
On monia tapoja toteuttaa prioriteettijonoja, kuten taulukoita ja linkitettyjä luetteloita. Nämä toteutukset voivat kuitenkin taata vain sen, että yksi lisäys- ja poistotoimista voidaan suorittaa O(1)O(1)-aikakompleksisuudessa, kun taas toinen toiminto on suoritettava loppuun O(N)O(N)-vaiheessa. aika monimutkaisuus. Keko voi mahdollistaa prioriteettijonon lisäystoiminnon suorittamisen loppuun O(log N)O(logN) aikamonimutkaisuuden sisällä ja poistotoiminnon suorittamisen O(log N)O(logN) aikamonimutkaisuuden sisällä. .

Kasa on erityinen binääripuu, joka täyttää seuraavat ehdot:

1. Täydellinen binääripuu (solmut sijoitetaan järjestyksessä vasemmalta oikealle);
2. Kunkin solmun arvon on oltava suurempi tai yhtä suuri tai pienempi tai yhtä suuri kuin sen alisolmun arvo.

Kasan ominaisuudet:

1. Elementit voidaan lisätä kasaan O(logN)-aikakompleksisuudessa;
2. Elementit voidaan poistaa kasosta O(logN)-aikakompleksisuudessa;
3. Kasan maksimi- tai minimiarvo voidaan saada O(1)-aikakompleksisuuden sisällä.

Kasojen luokitus:

Max keon: Jokaisen keon solmun arvo on suurempi tai yhtä suuri kuin sen alisolmun arvo. Max-keon ylin elementti (juurisolmu) on keon maksimiarvo.
Minimikeko: Keon jokaisen solmun arvo on pienempi tai yhtä suuri kuin sen alisolmun arvo. Min-keon ylin elementti (juurisolmu) on keon minimiarvo.
Nykyinen solmun numero on i, vasemman lapsen numero on 2i ja oikean lapsen numero on 2i+1.

ajan ja tilan monimutkaisuus

Kasan lajittelu

Teoria: Keon lajittelu viittaa keon tietorakenteen käyttämiseen järjestämättömien elementtien lajitteluun.

Min-heap -lajittelualgoritmin vaiheet ovat seuraavat:

Kasaa kaikki elementit minimikasaan;
Ota pois ja poista keon yläelementti ja sijoita keon yläelementti tietojoukkoon T, joka tallentaa järjestetyt elementit;
Tällä hetkellä kasa säädetään uuteen minimikasaan;
Toista vaiheita 3 ja 4, kunnes kasassa ei ole yhtään elementtiä.
Tässä vaiheessa saadaan uusi tietojoukko T, jossa elementit on järjestetty järjestykseen pienestä suureen.

Maksimikeon lajittelualgoritmin vaiheet ovat seuraavat:

Kasaa kaikki elementit maksimikasaan;
Ota pois ja poista keon yläelementti ja sijoita keon yläelementti tietojoukkoon T, joka tallentaa järjestetyt elementit;
Tällä hetkellä kasa säädetään uuteen maksimikekoon;
Toista vaiheita 3 ja 4, kunnes kasassa ei ole yhtään elementtiä.
Tässä vaiheessa saadaan uusi tietojoukko T, jossa elementit on järjestetty järjestykseen suuresta pieneen.
Aika monimutkaisuus: O (Nlog N). N on keon elementtien lukumäärä.

Avaruuden monimutkaisuus: O(N). N on keon elementtien lukumäärä.