Pochopte, ako implementovať binárnu haldu v prostredí Java

Tento článok vám poskytne kompletný prehľad o fungovaní haldy a neskôr sa naučíme implementovať binárnu haldu v Jave.

Program tohto článku je:

príkaz java na ukončenie programu

1. Čo je to halda?
2. Max. Halda
3. Min. Halda
4. Halda implementácia v Jave
   • Schéma
   • Zákonníka

Poďme začať!

Čo je to halda?

Halda je v podstate stromová dátová štruktúra. Má uzly. Uzol pozostáva z určitých prvkov. Každý uzol obsahuje jeden prvok.

Uzly môžu mať deti. Ak v prípade, že nie sú žiadne deti, nazýva sa to List.

Je potrebné dodržiavať dve pravidlá:

• Hodnota každého uzla musí byť menšia alebo rovnaká ako všetky hodnoty uložené v jeho podradených položkách.
• Má najmenšiu možnú výšku.

Hromady sú pri extrakcii extrémne efektívnenajmenší alebo najväčší prvok.

Prejdime teraz k minimálnej kope!

Min. Halda

Min halda je úplný binárny strom, v ktorom je hodnota koreňového prvku menšia alebo rovnaká ako ktorýkoľvek z podradených prvkov.

Zastúpenie min

Arr [(i-1) / 2]: toto vráti nadradený uzol.

Arr [(2 * i) + 1]: toto vráti ľavý dcérsky uzol.

Arr [(2 * i) + 2]: toto vráti správny podradený uzol.

Existujú určité metódy Min Heap:

• vložiť (): Nový kľúč je pridaný na koniec stromu. V prípade, že je nový kľúč väčší ako rodič, potom nie je potrebné robiť nič, inak musíme prejsť hore, aby sme nastavili vlastnosť haldy.
• getMin (): táto metóda pomáha vrátiť koreňový prvok.
• extractMin (): táto metóda vráti minimumprvok.

Teraz prechádzam na haldu Max.

Max hromada

Max. Halda je kompletný binárny strom, v ktorom je hodnota koreňového prvku väčšia alebo rovnaká ako ktorýkoľvek z podradených prvkov.

Max. Hromada tiež pozostáva z niekoľkých metód!

• Vložiť (): vloží prvok do haldy.
• Odstrániť () : vymaže prvok z haldy.
• FindMax (): nájde z haldy maximálny prvok.
• printHeap (): Vytlačí obsah haldy

Teraz vám ukážem implementáciu haldy prostredníctvom diagramu a neskôr Javakód.

Halda implementácia v Jave

Schéma:

Vyššie uvedený diagram zobrazuje binárnu haldu v prostredí Java. Ako ste sa dozvedeli, že existujú dve hromady: minimálna halda a maximálna halda, tu je diagram:

Teraz, keď sa presunieme k nášmu ďalšiemu segmentu, uvidíme, ako implementovať binárnu haldu v Jave.

Kód:

public class BinaryHeap {private static final int d = 2 private int [] halda private int heapSize / ** * Týmto sa inicializuje naša halda s predvolenou veľkosťou. * / public BinaryHeap (int kapacita) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Týmto sa skontroluje, či je halda prázdna alebo nie * Zložitosť: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Týmto sa skontroluje, či je halda plná alebo nie * Zložitosť: O (1) * / public boolean isFull () {return heapSize == halda .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * This will insert new element in to heap * Zložitosť: O (log N) * Ako najhorší scenár musíme prejsť do koreňového adresára * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert new element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Týmto sa vymaže prvok v indexe x * Zložitosť: O (log N) * * / public int delete (int x) {if (isEmpty ()) throw new NoSuchElementException ('Heap is empty, No element to delete') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Táto metóda sa používala na udržanie vlastnosti haldy pri vkladaní prvku. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} halda [i] = teplota} / ** * Táto metóda sa použila na udržanie vlastnosti haldy pri odstraňovaní prvku. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)halda [rightChild]? leftChild: rightChild} / ** * Táto metóda sa použila na tlač všetkých prvkov haldy * * / public void printHeap () {System.out.print ('nHeap =') pre (int i = 0 i
Týmto sa dostávame na koniec tohto článku o Binary Heap v Jave. Pozrite sa na    autor: Edureka, dôveryhodná online vzdelávacia spoločnosť so sieťou viac ako 250 000 spokojných študentov rozmiestnených po celom svete. Výcvikový a certifikačný kurz Edureka Java J2EE a SOA je určený pre študentov a profesionálov, ktorí chcú byť vývojármi Java. Kurz je navrhnutý tak, aby vám dal náskok v programovaní v Jave a naučil vás základné aj pokročilé koncepty Javy spolu s rôznymi rámcami Java, ako je Hibernate & Spring. 
príklad menného priestoru c ++
 Máte na nás otázku? Uveďte to, prosím, v sekcii komentárov tohto blogu „Java ArrayList“ a my sa vám ozveme čo najskôr.