Ismerje meg a bináris halom megvalósítását a Java-ban

Ez a cikk részletes és átfogó tudást nyújt Önnek arról, hogyan lehet bináris kupacot bevezetni a java-ban példákkal.

Ez a cikk teljes áttekintést nyújt a halom rendezésének működéséről, később pedig megtanuljuk a bináris halom implementálását a Java-ban.



Íme a cikk napirendje:



  1. Mi a halomfajta?
  2. Max Heap
  3. Min Heap
  4. Halom implementáció Java-ban
    • Diagram
    • Kód

Kezdjük!

Mi a halomfajta?

A halom alapvetően egy fa alapú adatszerkezet. Csomópontjai vannak. A csomópont bizonyos elemeket tartalmaz. Minden csomópont egy elemet tartalmaz.



A csomópontoknak lehetnek gyermekeik. Ha nincsenek gyerekek, akkor ezt levélnek hívják.

c ++ goto nyilatkozat

Két szabályt kell betartani:

  • Minden csomópont értékének kisebbnek vagy egyenlőnek kell lennie a gyermekeiben tárolt összes értékkel.
  • A lehető legkisebb magasságú.

A halmok rendkívül hatékonyan nyerik ki a legkisebb vagy legnagyobb elem.



Térjünk át most a min kupacra!

Min Heap

A Min halom egy teljes bináris fa, amelyben a gyökérelem értéke kisebb vagy egyenlő a gyermekelem bármelyikével.

Min halom ábrázolása

Arr [(i-1) / 2]: ez visszaadja a szülőcsomópontot.

Arr [(2 * i) + 1]: ez visszaadja a bal gyermekcsomópontot.

Arr [(2 * i) + 2]: ez visszaadja a megfelelő gyermek csomópontot.

A Min Heap bizonyos módszerei vannak:

  • beillesztés (): Új kulcs kerül a fa végére. Abban az esetben, ha az új kulcs nagyobb, mint a szülő, akkor nincs szükség semmire, különben fel kell haladnunk a kupac tulajdonság beállításához.
  • getMin (): ez a módszer segít a gyökérelem visszaadásában.
  • extractMin (): ez a módszer a minimumot adja vissza elem.

Most továbbhaladok Max halomba.

tábla egy táblázaton belül html

Max halom

A Max halom egy teljes bináris fa, amelyben a gyökérelem értéke nagyobb vagy egyenlő a gyermekelem bármelyikével.

A Max halom többféle módszerből is áll!

  • Beszúrás (): egy elemet illeszt be a kupacba.
  • Töröl() : töröl egy elemet a kupacból.
  • FindMax (): meg fogja találni a maximális elemet a kupacból.
  • printHeap (): Kinyomtatja a kupac tartalmát

Most hadd mutassam meg a kupac megvalósítását egy diagram, majd később egy Java segítségével kód.

Halom implementáció Java-ban

Diagram:

Heap

A fenti ábra a Java bináris halmát mutatja. Amint megtudta, hogy két kupac létezik: Min kupac és Max kupac, íme egy ábra:

Most a következő szegmensünkre lépve meglátjuk, hogyan lehet bináris halmot megvalósítani a Java-ban.

Kód:

public class BinaryHeap {private static final int d = 2 private int [] kupac private int heapSize / ** * Ez inicializálja a kupacunkat az alapértelmezett mérettel. * / public BinaryHeap (int kapacitás) {heapSize = 0 kupac = new int [kapacitás + 1] Tömbök.kitöltés (halom, -1)} / ** * Ez ellenőrzi, hogy a kupac üres-e vagy sem * Komplexitás: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Ez ellenőrzi, hogy a halom tele van-e vagy sem * Komplexitás: O (1) * / public boolean isFull () {return heapSize == heap .length} private int szülő (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Ez új elemet illeszt be a kupacba * Komplexitás: O (log N) * Legrosszabb esetben a gyökérig kell haladnunk * / public void insert (int x) {if (isFull ()) dobjon új NoSuchElementException-t ('A kupac megtelt, Nincs hely beszúrásra új elem ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Ez törli az x index elemét * Komplexitás: O (log N) * * / public int delete (int x) {if (isEmpty ()) dob új NoSuchElementException ('A kupac üres, nincs törölhető elem') int kulcs = kupac [x] kupac [x] = kupac [heapSize -1] heapSize-- heapifyDown (x) retu rn kulcs} / ** * Ez a módszer a kupac tulajdonság fenntartására szolgál, miközben egy elemet beilleszt. * * / private void heapifyUp (int i) {int temp = kupac [i] while (i> 0 && temp> kupac [szülő (i)]) {kupac [i] = kupac [szülő (i)] i = szülő (i)} kupac [i] = temp} / ** * Ez a módszer a kupac tulajdonság fenntartására szolgál, miközben elemet töröl. * * / private void heapifyDown (int i) {int gyermek int temp = halom [i] while (kthChild (i, 1)kupac [rightChild]? leftChild: rightChild} / ** * Ez a módszer a kupac * * / public void printHeap () {System.out.print ('nHeap =') összes elemének kinyomtatására (int i = 0 i

Ezzel véget értünk a Java bináris halmáról szóló cikkünknek. Nézze meg a az Edureka, egy megbízható online tanulási vállalat, amelynek több mint 250 000 elégedett tanulóval rendelkező hálózata elterjedt az egész világon. Az Edureka Java J2EE és SOA képzési és tanúsítási tanfolyamát olyan hallgatók és szakemberek számára tervezték, akik Java fejlesztők szeretnének lenni. A tanfolyamot úgy tervezték meg, hogy előrelépést nyújtson a Java programozásban, és képezze mind az alapvető, mind a fejlett Java koncepciókhoz, valamint a különböző Java keretrendszerekhez, például a Hibernate & Spring.

Van egy kérdésünk? Kérjük, említse meg a „Java ArrayList” blog megjegyzés rovatában, és a lehető leghamarabb kapcsolatba lépünk Önnel.