A Pino on erikoista täydellinen binääripuu . Koska kasa on täydellinen binääripuu, kasa on N solmuissa on log N korkeus. On hyödyllistä poistaa korkeimman tai alimman prioriteetin elementti. Se esitetään tyypillisesti muodossa joukko . Pinoissa on kahdenlaisia kasojaMin-Heap
Jonkin sisällä Min-Heap juurisolmussa olevan avaimen on oltava pienempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. Saman ominaisuuden on oltava rekursiivisesti totta kaikille kyseisen binaaripuun alipuille. Min-Heapissa juuressa oleva vähimmäisavainelementti. Alla on binaaripuu, joka täyttää kaiken Min Kasan omaisuuden.
Max Heap
Jonkin sisällä Max-Heap juurisolmussa olevan avaimen on oltava suurempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. Saman omaisuuden tulee olla rekursiivisesti totta kaikille tuon binaaripuun alipuille. Max-Keapissa juuressa oleva suurin avainelementti. Alla on binääripuu, joka täyttää kaikki Max Heapin omaisuudet.
Ero Min-keon ja Max-keon välillä
| Min Kasko | Max Heap | |
|---|---|---|
| 1. | Min-Keapissa juurisolmussa olevan avaimen on oltava pienempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. | Max-Keapissa juurisolmussa olevan avaimen on oltava suurempi tai yhtä suuri kuin kaikissa sen lapsissa olevien avainten joukossa. |
| 2. | Min-Heapissa juuressa oleva vähimmäisavainelementti. | Max-Keapissa juuressa oleva suurin avainelementti. |
| 3. | Min-Heap käyttää nousevaa prioriteettia. | Max-Heap käyttää laskevaa prioriteettia. |
| 4. | Min-Heapin rakenteessa pienin elementti on etusijalla. | Max-Heapin rakenteessa suurin elementti on etusijalla. |
| 5. | Min-keossa pienin elementti ponnahtaa ensimmäisenä kasasta. | Max-Keossa suurin elementti ponnahtaa kasasta ensimmäisenä. |
Kasan sovellukset :
- Keon lajittelu : Heap Sort on yksi parhaista käyttävistä lajittelualgoritmeista Binäärikeko to lajittele joukko sisään O(N*log N) aika.
- Prioriteettijono : Prioriteettijono voidaan toteuttaa käyttämällä kasaa, koska se tukee insert() , poistaa() , ekstraktiMax() , vähentääKey() operaatiot sisään O(log N) aika.
- Dijkstran lyhin polku ja Primin vähimmäisvirityspuu .
Min-Heapin ja Max-Heapin suorituskykyanalyysi :
- Hanki enimmäis- tai vähimmäiselementti: O(1)
- Lisää elementti Max-Keap- tai Min-Keap-kenttään: O(log N)
- Poista enimmäis- tai vähimmäiselementti: O(log N)