Tämä artikkeli antaa sinulle täydellisen yleiskatsauksen kasan lajittelun toiminnasta ja myöhemmin opimme toteuttamaan binaarisen kasan Java-sovelluksessa.
Tässä on tämän artikkelin esityslista:
Aloitetaanpa!
Mikä on kasan lajittelu?
Heap on pohjimmiltaan puupohjainen tietorakenne. Siinä on solmuja. Solmu koostuu tietyistä elementeistä. Jokainen solmu sisältää yhden elementin.
Solmuilla voi olla lapsia. Jos lapsia ei ole, sitä kutsutaan lehdeksi.
lajittelutoiminto c ++
Noudatettavia sääntöjä on kaksi:
- Jokaisen solmun arvon on oltava pienempi tai yhtä suuri kuin kaikki lapsiin tallennetut arvot.
- Sen korkeus on pienin mahdollinen.
Kasat ovat erittäin tehokkaita uuttamallapienin tai suurin elementti.
Siirrytään nyt min kasaan!
Min kasa
Min kasa on täydellinen binääripuu, jossa juurielementin arvo on pienempi tai yhtä suuri kuin jompikumpi alielementti.
Minin kasan esitys
Arr [(i-1) / 2]: tämä palauttaa ylätason solmun.
Arr [(2 * i) + 1]: tämä palauttaa vasemman lapsisolmun.
Arr [(2 * i) + 2]: tämä palauttaa oikean lapsisolmun.
Min Heapille on olemassa tiettyjä menetelmiä:
- lisää (): Uusi avain puun päähän lisätään. Jos uusi avain on isompi kuin vanhempi, meidän ei tarvitse tehdä mitään, muuten meidän on kuljettava ylös kasan ominaisuuden määrittämiseksi.
- getMin (): tämä menetelmä auttaa palauttamaan juurielementin.
- extractMin (): tämä menetelmä palauttaa pienimmänelementti.
Siirtyminen Max-kasaan nyt.
kuinka muuntaa kaksinkertainen int
Max kasa
Suurin kasa on täydellinen binääripuu, jossa juurielementin arvo on suurempi tai yhtä suuri kuin jompikumpi alielementti.
Max kasa koostuu myös useista menetelmistä!
- Lisää (): se lisää elementin kasaan.
- Poistaa() : se poistaa elementin kasasta.
- FindMax (): se löytää maksimaalisen elementin kasasta.
- printHeap (): Se tulostaa kasan sisällön
Sallikaa minun nyt näyttää kasan toteutus kaavion ja myöhemmin Java: n avullakoodi.
Kasan toteutus Java: ssa
Kaavio:
Yllä oleva kaavio näyttää Java-binaarisen kasan. Kuten olet oppinut, että on olemassa kaksi kasaa: Min kasa ja Max kasa, tässä on kaavio:
Nyt, siirtymällä seuraavaan segmenttiin, näemme, kuinka binaarinen kasa toteutetaan Javassa.
Koodi:
public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Tämä alustaa kasan oletuskoolla. * / public BinaryHeap (int-kapasiteetti) {heapSize = 0 kasa = uusi int [kapasiteetti + 1] matriisit.täyttö (kasa, -1)} / ** * Tämä tarkistaa onko kasa tyhjä vai ei * Monimutkaisuus: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Tämä tarkistaa, onko kasa täynnä vai ei * Complexity: O (1) * / public boolean isFull () {return heapSize == heap .length} yksityinen int vanhempi (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Tämä lisää uuden elementin kasaan * Monimutkaisuus: O (log N) * Pahimmassa tapauksessa meidän on kuljettava juuresta saakka * / public void insert (int x) {if (isFull ()) heittää uuden NoSuchElementException ('Kasa on täynnä, ei tilaa lisätä uusi elementti ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Tämä poistaa elementin hakemistosta x * Monimutkaisuus: O (log N) * * / public int delete (int x) {if (isEmpty ()) heittää uusi NoSuchElementException ('Kasa on tyhjä, ei poistettavaa elementtiä') int avain = kasa [x] kasa [x] = kasa [heapSize -1] heapSize-- heapifyDown (x) rn-avain} / ** * Tätä menetelmää käytetään ylläpitämään kasan ominaisuutta samalla kun lisätään elementti. * * / private void heapifyUp (int i) {int temp = kasa [i] while (i> 0 && temp> kasa [vanhempi (i)]) {kasa [i] = kasa [vanhempi (i)] i = vanhempi (i)} kasa [i] = temp} / ** * Tätä menetelmää käytetään ylläpitämään kasan ominaisuutta samalla kun poistetaan elementti. * * / private void heapifyDown (int i) {int lapsi int temp = kasa [i] while (kthChild (i, 1)kasa [rightChild]? leftChild: rightChild} / ** * Tätä menetelmää käytettiin kasan kaikkien elementtien * * / public void printHeap () {System.out.print ('nHeap =') tulostamiseen (int i = 0 i)Tämän avulla olemme päässeet tämän Java-binaarista kasaa koskevan artikkelin loppuun. Katso Edureka, luotettava verkko-oppimisyritys, jolla on yli 250 000 tyytyväisen oppijan verkosto, joka levisi ympäri maailmaa. Edurekan Java J2EE- ja SOA-koulutus- ja sertifiointikurssi on suunniteltu opiskelijoille ja ammattilaisille, jotka haluavat olla Java-kehittäjiä. Kurssi on suunniteltu antamaan sinulle etumatka Java-ohjelmointiin ja kouluttamaan sekä ydin- että edistyneitä Java-konsepteja sekä erilaisia Java-kehyksiä, kuten Hibernate & Spring.
Onko sinulla kysymys meille? Mainitse se tämän Java ArrayList -blogin kommenttiosassa, niin otamme sinuun yhteyttä mahdollisimman pian.