Kasasta käytetään nimitystä 'osittain tilattu' eikä 'osittain lajiteltu'. Sana 'lajitella' tarkoittaa täydellistä järjestystä (täydellinen lajittelu). Kasaa ei tilata osittain mielivaltaisesti. Kasa on osittain järjestetty alla olevan kriteerin (kuvion) mukaisesti.
Kasalajittelu koostuu siis kahdesta vaiheesta: kasan rakentamisesta ja järjestetyn elementin poistamisesta kasan huipulta. Toisessa vaiheessa, jokaisen poiston jälkeen, kasa rakennetaan uudelleen. Jokainen uudelleenrakennus on nopeampi kuin alkuperäinen rakennusprosessi, koska uudelleenrakentaminen tehdään edellisestä rakennuksesta, jossa yksi elementti on poistettu. Ja sen avulla heapsort lajittelee täysin lajittelemattoman luettelon.
Tämän artikkelin tarkoituksena on selittää lyhyesti kasalajittelua ja sitten tuottaa sen aikamonimutkaisuus (katso ajan monimutkaisuuden merkitys alla). Loppua kohden koodaus tehdään C++:lla.
Minimi kasa
Kasa voi olla minimi- tai maksimikasa. Max-keko on sellainen, jossa ensimmäinen elementti on korkein elementti ja koko puu tai vastaava lista on järjestetty osittain laskevassa järjestyksessä. Vähimmäiskeko on sellainen, jossa ensimmäinen elementti on pienin elementti ja koko lista on osittain järjestetty nousevaan järjestykseen. Tässä artikkelissa tarkastellaan vain vähimmäiskasaa. Huomaa: kasan aiheessa elementtiä kutsutaan myös solmuksi.
Kasa on täydellinen binääripuu. Binääripuu voidaan ilmaista taulukona (luettelona); lue ylhäältä alas ja vasemmalta oikealle. Min-keon keon ominaisuus on, että emosolmu on pienempi tai yhtä suuri kuin kumpikin sen kahdesta lapsista. Esimerkki järjestämättömästä luettelosta on:
| 9 | 19 | 24 | 5 | 3 | yksitoista | 14 | 22 | 7 | 6 | 17 | viisitoista | tyhjä | tyhjä | tyhjä |
| 0 | 1 | kaksi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista | 12 | 13 | 14 |
Tämän taulukon ensimmäinen rivi on taulukon elementit. Toisella rivillä ovat nollaperusteiset indeksit. Tämä elementtiluettelo voidaan ilmaista puuna. Nollaelementit on lisätty täydellisen binääripuun luomiseksi. Tarkkaan ottaen nollaelementit eivät ole osa luetteloa (puuta). Tällä listalla ei ole järjestystä, joten se ei ole vielä kasa. Siitä tulee kasa, kun se on osittain tilattu kasan ominaisuuden mukaan.
Solmujen ja indeksien välinen suhde
Muista, että kasa on täydellinen binääripuu ennen keon konfiguraatiota (keon ominaisuus). Edellinen lista ei ole vielä kasa, koska elementit eivät noudata pinon ominaisuutta. Siitä tulee kasa, kun elementit on järjestetty osittaiseen järjestykseen min-keon ominaisuuden mukaan. Osittainen järjestys voidaan nähdä osittaisena lajitteluna (vaikka sana 'lajittelu' tarkoittaa täydellistä järjestystä).
Olipa binääripuu kasa vai ei, jokaisella vanhemmalla on kaksi lasta paitsi lehtien (viimeiset) solmut. Indeksien välillä on matemaattinen suhde kunkin vanhemman ja sen lasten välillä. Se on seuraava: Jos vanhempi on indeksissä i, niin vasen lapsi on indeksissä:
kaksi * i + 1ja oikea lapsi on indeksissä:
kaksi * i + kaksiTämä on nollapohjaista indeksointia varten. Ja niin, vanhemman, joka on indeksissä 0, on vasen lapsi indeksissä 2×0+1=1 ja oikea lapsi 2×0+2=2. Indeksin 1 vanhemman vasen lapsi on indeksissä 2×1+1=3 ja oikea lapsi indeksissä 2×1+2=4; ja niin edelleen.
Min-keap-ominaisuuden mukaan vanhempi kohdassa i on pienempi tai yhtä suuri kuin vasen lapsi kohdassa 2i+1 ja pienempi tai yhtä suuri kuin oikea lapsi kohdassa 2i+2.
Pino
Kasaaminen tarkoittaa kasan rakentamista. Se tarkoittaa luettelon (tai vastaavan puun) elementtien järjestämistä uudelleen niin, että ne täyttävät kasan ominaisuuden. Kasoitusprosessin lopussa luettelo tai puu on kasa.
Jos edellinen lajittelematon luettelo on pinottu, siitä tulee:
| 3 | 5 | yksitoista | 7 | 6 | viisitoista | 14 | 22 | 9 | 19 | 17 | 24 | tyhjä | tyhjä | tyhjä |
| 0 | 1 | kaksi | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | yksitoista | 12 | 13 | 14 |
Huomautus: luettelossa on 12 elementtiä, ei 15. Toisella rivillä ovat indeksit. Kasan rakentamisprosessissa elementit piti tarkistaa ja osa vaihtaa.
Huomaa, että pienin ja ensimmäinen alkio on 3. Muut alkiot seuraavat nousevasti, mutta aaltoilevasti. Jos vasen ja oikea lapsi paikoissa 2i+1 ja 2i+2 ovat kumpikin suurempia tai yhtä suuria kuin vanhempi kohdassa i, tämä on min-kasa. Tämä ei ole täyttä tilaamista tai lajittelua. Tämä on osittainen tilaus kasan ominaisuuden mukaan. Tästä alkaa seuraava kasojen lajitteluvaihe.
Kasvata ajan monimutkaisuutta
Aika monimutkaisuus on jonkin koodin suhteellinen ajoaika. Se voidaan nähdä koodin suorittamiseen tarvittavien päätoimintojen lukumääränä. Kasan rakentamiseen on erilaisia algoritmeja. Tehokkaimmat ja nopeimmat jakavat listan jatkuvasti kahdella, tarkistavat elementit alhaalta ja vaihtavat sitten elementtejä. Olkoon N käytännön elementtien lukumäärä luettelossa. Tällä algoritmilla pääoperaatioiden (vaihto) enimmäismäärä on N. Kasauksen aikamonimutkaisuus on annettu aiemmin seuraavasti:
O ( n )Missä n on N ja on suurin mahdollinen päätoimintojen lukumäärä. Tätä merkintää kutsutaan Big-O-merkinnällä. Se alkaa O:lla isoilla kirjaimilla ja sen jälkeen suluilla. Suluissa on lauseke mahdolliselle suurimmalle määrälle operaatioita.
Muista: yhteenlaskemisesta voi tulla kertolasku, jos sama lisättävä asia toistuu.
Heapsort kuvitus
Edellistä lajittelematonta luetteloa käytetään havainnollistamaan kasalajittelua. Annettu lista on:
9 19 24 5 3 yksitoista 14 22 7 6 17 viisitoistaListasta tuotettu minimikeko on:
3 5 yksitoista 7 6 viisitoista 14 22 9 19 17 24Kasalajittelun ensimmäinen vaihe on tuottaa kasa, joka on tuotettu. Tämä on osittain järjestetty luettelo. Se ei ole lajiteltu (täysin lajiteltu) luettelo.
Toinen vaihe koostuu vähiten elementin, joka on ensimmäinen elementti, poistaminen kasasta, jäljellä olevan kasan uudelleenkasaaminen ja tulosten vähiten elementtien poistaminen. Vähiten elementti on aina uudelleen kasotetun kasan ensimmäinen elementti. Elementtejä ei poisteta ja heittää pois. Ne voidaan lähettää eri matriisiin siinä järjestyksessä, jossa ne poistetaan.
Lopulta uudessa taulukossa kaikki elementit olisi lajiteltu (täysin), nousevaan järjestykseen; eikä enää vain osittain tilattu.
Toisessa vaiheessa ensimmäinen asia on poistaa 3 ja sijoittaa se uuteen taulukkoon. Tulokset ovat:
3ja
5 yksitoista 7 6 viisitoista 14 22 9 19 17 24Loput elementit on pinottava ennen kuin ensimmäinen elementti poistetaan. Jäljellä olevien elementtien kasa voi olla:
5 6 7 9 viisitoista 14 22 yksitoista 19 17 24Poimimalla 5 ja lisäämällä uuteen luetteloon (taulukkoon) saadaan tulokset:
3 5ja
6 7 9 viisitoista 14 22 yksitoista 19 17 24Jäljellä olevan sarjan kasaaminen antaisi:
6 7 9 viisitoista 14 22 yksitoista 19 17 24Poimimalla 6 ja lisäämällä uuteen luetteloon (taulukkoon) saadaan tulokset:
3 5 6ja
7 9 viisitoista 14 22 yksitoista 19 17 24Jäljellä olevan sarjan kasaaminen antaisi:
7 9 yksitoista 14 22 viisitoista 19 17 24Poimimalla 7 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7ja
9 yksitoista 14 22 viisitoista 19 17 24Jäljellä olevan sarjan kasaaminen antaa:
9 yksitoista 14 22 viisitoista 19 17 24Poimimalla 9 ja lisäämällä uuteen luetteloon saadaan tulokset:
3 5 6 7 9ja
yksitoista 14 22 viisitoista 19 17 24Jäljellä olevan sarjan kasaaminen antaa:
yksitoista 14 17 viisitoista 19 22 24Poimimalla 11 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoistaja
14 17 viisitoista 19 22 24Jäljellä olevan sarjan kasaaminen antaisi:
14 17 viisitoista 19 22 24Poimimalla 14 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14ja
17 viisitoista 19 22 24Jäljellä olevan sarjan kasaaminen antaisi:
viisitoista 17 19 22 24Poimimalla 15 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14 viisitoistaja
17 19 22 24Jäljellä olevan sarjan kasaaminen antaisi:
17 19 22 24Poimimalla 17 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14 viisitoista 17ja
19 22 24Jäljellä olevan sarjan kasaaminen antaisi:
19 22 24Poimimalla 19 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14 viisitoista 17 19ja
22 24Jäljellä olevan sarjan kasaaminen antaa:
22 24Poimimalla 22 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14 viisitoista 17 19 22ja
24Jäljellä olevan sarjan kasaaminen antaa:
24Poimimalla 24 ja lisäämällä sen uuteen luetteloon saadaan tulokset:
3 5 6 7 9 yksitoista 14 viisitoista 17 19 22 24ja
- - -Kekotaulukko on nyt tyhjä. Kaikki sen alussa olleet elementit ovat nyt uudessa taulukossa (luettelossa) ja lajiteltuina.
Heapsort-algoritmi
Vaikka lukija on saattanut lukea oppikirjoista, että kasalajittelu koostuu kahdesta vaiheesta, kekolajittelun voidaan silti nähdä koostuvan yhdestä vaiheesta, joka iteratiivisesti kutistuu pois annetusta taulukosta. Tämän avulla lajittelun algoritmi kasalajittelulla on seuraava:
- Kasaa lajittelematon luettelo.
- Pura keon ensimmäinen elementti ja laita se uuden luettelon ensimmäiseksi elementiksi.
- Kasaa jäljellä oleva luettelo.
- Pura uuden keon ensimmäinen elementti ja aseta se uuden luettelon seuraavaksi elementiksi.
- Toista edelliset vaiheet järjestyksessä, kunnes kasaluettelo on tyhjä. Lopulta uusi lista lajitellaan.
Kekolajittelun ajan monimutkaisuus Proper
Yksivaiheista lähestymistapaa käytetään määrittämään kasalajittelun aika monimutkaisuus. Oletetaan, että lajitellaan 8 lajittelematonta elementtiä.
Mahdollinen enimmäismäärä toimintojen kasaamista 8 elementtejä on 8 .The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 7 elementtejä on 7 .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 6 elementtejä on 6 .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 5 elementtejä on 5 .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 4 elementtejä on 4 .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 3 elementtejä on 3 .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi kaksi elementtejä on kaksi .
The mahdollinen enimmäismäärä operaatioita jäljellä olevien kasaamiseksi 1 elementti on 1 .
Operaatioiden mahdollinen enimmäismäärä on:
8 + 7 + 6 + 5 + 4 + 3 + kaksi + 1 = 36Näiden toimintojen lukumäärän keskiarvo on:
36 / 8 = 4.5Huomaa, että edellisen kuvan neljä viimeistä kasaa eivät muuttuneet, kun ensimmäinen elementti poistettiin. Jotkut aiemmista kasoista eivät myöskään muuttuneet, kun ensimmäinen elementti poistettiin. Tällöin parempi keskimääräinen pääoperaatioiden (vaihtojen) lukumäärä on 3 eikä 4,5. Joten parempi keskimääräinen päätoimintojen kokonaismäärä on:
24 = 8 x 3=> 24 = 8 x Hirsi < sub > kaksi < / sub > 8
lokista lähtien kaksi 8 = 3.
Yleensä kasalajin tapauksen keskimääräinen aika monimutkaisuus on:
O ( n. log2n )Kun piste tarkoittaa kertolaskua ja n on N, listan (joko luettelon) elementtien kokonaismäärä.
Huomaa, että ensimmäisen elementin purkaminen on ohitettu. Ajan monimutkaisuudesta puhuttaessa toiminnot, jotka vievät suhteellisen vähän aikaa, jätetään huomiotta.
Koodaus C++:lla
C++:n algoritmikirjastossa on make_heap()-funktio. Syntaksi on:
sapluuna < luokkaa RandomAccessIterator, luokkaa Vertailla >constexpr mitätön make_heap ( RandomAccessIterator ensin, RandomAccessIterator viimeisenä, Vertaa comp ) ;
Se ottaa vektorin ensimmäiseen elementtiin osoittavan iteraattorin ensimmäiseksi argumentiksi ja sitten juuri vektorin lopun taakse osoittavan iteraattorin viimeisenä argumenttina. Edellisessä lajittelemattomassa luettelossa syntaksia käytettäisiin seuraavasti vähimmäiskeon saamiseksi:
vektori < int > vtr = { 9 , 19 , 24 , 5 , 3 , yksitoista , 14 , 22 , 7 , 6 , 17 , viisitoista } ;vektori < int > :: iteraattori iterB = vtr. alkaa ( ) ;
vektori < int > :: iteraattori iterE = vtr. loppu ( ) ;
make_heap ( iterB, iterE, suurempi < int > ( ) ) ;
Tämä koodi muuttaa vektorisisällön minimikekokonfiguraatioksi. Seuraavissa C++-vektoreissa käytetään kahta vektoria kahden taulukon sijaan.
Voit kopioida ja palauttaa vektorin ensimmäisen elementin käyttämällä vektorin syntaksia:
constexpr referenssirintama ( ) ;Voit poistaa vektorin ensimmäisen elementin ja heittää sen pois käyttämällä vektorin syntaksia:
constexpr iteraattorin poisto ( const_iterator sijainti )Jos haluat lisätä elementin vektorin taakse (seuraava elementti), käytä vektorin syntaksia:
constexpr mitätön työnnä takaisin ( konst T & x ) ;Ohjelman alku on:
#include#include
#sisällytä
käyttämällä nimiavaruus std ;
Algoritmi ja vektorikirjastot ovat mukana. Seuraavaksi ohjelmassa on heapsort()-funktio, joka on:
mitätön kasalajitella ( vektori < int > & vanhaV, vektori < int > & uusi V ) {jos ( vanha V. koko ( ) > 0 ) {
vektori < int > :: iteraattori iterB = vanha V. alkaa ( ) ;
vektori < int > :: iteraattori iterE = vanha V. loppu ( ) ;
make_heap ( iterB, iterE, suurempi < int > ( ) ) ;
int Seuraava = vanha V. edessä ( ) ;
vanha V. pyyhkiä ( iterB ) ;
uusi V. työnnä takaisin ( Seuraava ) ;
kasalajitella ( vanha V, uusi V ) ;
}
}
Se on rekursiivinen funktio. Se käyttää C++-algoritmikirjaston make_heap()-funktiota. Funktiomäärityksen toinen koodisegmentti poimii ensimmäisen elementin vanhasta vektorista kasan rakentamisen jälkeen ja lisää seuraavan elementin uudelle vektorille. Huomaa, että funktion määrittelyssä vektoriparametrit ovat viitteitä, kun taas funktiota kutsutaan tunnisteiden (nimien) kanssa.
Sopiva C++-päätoiminto tähän on:
int pää ( int argc, hiiltyä ** argv ){
vektori < int > vanha V = { 9 , 19 , 24 , 5 , 3 , yksitoista , 14 , 22 , 7 , 6 , 17 , viisitoista } ;
vektori < int > uusi V ;
kasalajitella ( vanha V, uusi V ) ;
varten ( int i = 0 ; i < uusi V. koko ( ) ; i ++ ) {
cout << uusi V [ i ] << '' ;
}
cout << endl ;
palata 0 ;
}
Lähtö on:
3 5 6 7 9 yksitoista 14 viisitoista 17 19 22 24lajiteltu (täysin).
Johtopäätös
Artikkelissa käsiteltiin yksityiskohtaisesti Heap Sort -toiminnon luonnetta ja toimintaa, joka tunnetaan yleisesti nimellä Heapsort, lajittelualgoritmina. Heapify Time Complexity, Heapsort illustration ja Heapssort algoritmi käsiteltiin ja tuettiin esimerkeillä. Hyvin kirjoitetun kasalajitteluohjelman keskimääräinen aika monimutkaisuus on O(nlog(n))