Pino vs. kasa
Pino on järjestetty luettelo, johon listan kohteiden lisääminen ja poistaminen voidaan tehdä vain yhdessä päässä, jota kutsutaan yläosaksi. Tästä syystä pinoa pidetään Last in First out (LIFO) -tietorakenteena. Kasa on erityinen puurakenteinen tietorakenne, joka täyttää erityisomaisuuden, jota kutsutaan kasan ominaisuudeksi. Kasa on myös täydellinen puu, mikä tarkoittaa, että puun lehtien välillä ei ole aukkoja, eli kokonaisessa puussa jokainen taso täytetään ennen uuden tason lisäämistä puuhun ja tietyn tason solmut täytetään vasemmalta oikealle.
Mikä on pino?
Kuten aiemmin mainittiin, pino on tietorakenne, jossa elementtejä lisätään ja poistetaan vain yhdestä päästä, jota kutsutaan yläosaksi. Pinot sallivat vain kaksi perustoimintoa, joita kutsutaan push and popiksi. Työntö lisää uuden elementin pinon yläosaan. Pop-toiminto poistaa elementin pinon yläosasta. Jos pino on jo täynnä, työntöoperaation aikana sitä pidetään pinon ylivuotona. Jos pop-operaatio suoritetaan jo tyhjälle pinolle, sitä pidetään pinon alivuotona. Pinoon suoritettavien toimintojen pienen määrän vuoksi sitä pidetään rajoitettuna tietorakenteena. Lisäksi push- ja pop-operaatioiden määrittelytavan mukaan on selvää, että pinoon viimeiseksi lisätyt elementit menevät ensin pinosta. Siksi pinoa pidetään LIFO-tietorakenteena.
Mikä on kasa?
Kuten aiemmin mainittiin, kasa on täydellinen puu, joka täyttää kasan ominaisuuden. Kasan ominaisuus kertoo, että jos y on x: n alisolmu, solmuun x tallennetun arvon tulisi olla suurempi tai yhtä suuri kuin solmuun y tallennettu arvo (eli arvo (x) ≥ arvo (y)). Tämä ominaisuus tarkoittaa, että suurin arvoinen solmu sijoitettaisiin aina juurelle. Tätä ominaisuutta käyttäen rakennettua kasaa kutsutaan max-kasaksi. Kasan omaisuudessa on toinen muunnelma, joka ilmoittaa tämän päinvastaisen. (eli arvo (x) ≤ arvo (y)). Tämä tarkoittaa, että solmu, jolla on pienin arvo, sijoitettaisiin aina juurelle, jota täten kutsutaan min-kasaksi. Kasoilla suoritetaan laaja valikoima toimintoja, kuten minimin (min-kasoissa) tai maksimien (max-kasoissa) löytäminen, minimien (min-kasoissa) tai maksimien (max-kasoissa) poistaminen,kasvava (max-kasoissa) tai laskeva (min-heaps) -avain jne.
Mitä eroa on pinolla ja kasalla?
Suurin ero pinojen ja kasojen välillä on, että vaikka pino on lineaarinen tietorakenne, kasa on epälineaarinen tietorakenne. Pino on järjestetty luettelo, joka seuraa LIFO-ominaisuutta, kun taas kasa on täydellinen puu, joka seuraa kasan ominaisuutta. Lisäksi pino on rajoitettu tietorakenne, joka tukee vain rajoitettua määrää toimintoja push ja pop -toimintona, kun taas kasa tukee monenlaisia toimintoja, kuten minimin tai maksimin löytäminen ja poistaminen, avaimen lisääminen tai pienentäminen ja yhdistäminen.
