Înțelegeți cum să implementați o grămadă binară în Java

Acest articol vă va oferi o imagine de ansamblu completă a funcționării tipului de heap și, mai târziu, vom învăța să implementăm un Heap Binar în Java.

Iată agenda acestui articol:

1. Ce este sortul heap?
2. Max Heap
3. Min Heap
4. Implementare Heap în Java
   • Diagramă
   • Cod

Sa incepem!

Ce este sortul heap?

Heap este practic o structură de date bazată pe copac. Are noduri. Nodul cuprinde anumite elemente. Fiecare nod conține un element.

matrice de sortare c ++

Nodurile pot avea copii. Dacă în cazul în care nu există copii, se numește Frunză.

Există două reguli care trebuie respectate:

• Valoarea fiecărui nod trebuie să fie mai mică sau egală cu toate valorile stocate în copiii săi.
• Are înălțimea cea mai mică posibilă.

Greutățile sunt extrem de eficiente în extragereacel mai mic sau cel mai mare element.

Să trecem acum la min heap!

Min Heap

Min heap este un arbore binar complet în care valoarea elementului rădăcină este mai mică sau egală cu oricare dintre elementele copil.

Reprezentarea min heap

diferență între bigdata și hadoop

Arr [(i-1) / 2]: aceasta va returna nodul părinte.

Arr [(2 * i) + 1]: aceasta va returna nodul copil stâng.

Arr [(2 * i) + 2]: aceasta va returna nodul copil potrivit.

Există anumite metode de Min Heap:

• introduce(): Se adaugă o nouă cheie la capătul arborelui. În cazul în care noua cheie este mai mare decât părintele, atunci nu este nevoie să facem nimic, altfel, trebuie să traversăm pentru a configura proprietatea heap.
• getMin (): această metodă ajută la returnarea elementului rădăcină.
• extractMin (): această metodă returnează minimulelement.

Trecând la heap-ul Max acum.

Heap maxim

Heapul maxim este un arbore binar complet în care valoarea elementului rădăcină este mai mare sau egală cu oricare dintre elementele copil.

Heapul maxim constă și din mai multe metode!

arhitectura mvc în java cu exemplu

• Inserați (): va introduce un element în heap.
• Șterge() : va șterge un element din heap.
• FindMax (): va găsi elementul maxim din grămadă.
• printHeap (): Acesta va imprima conținutul heap-ului

Acum permiteți-mi să vă arăt implementarea heap printr-o diagramă și mai târziu printr-un Javacod.

Implementare Heap în Java

Diagramă:

Diagrama de mai sus arată heap-ul binar în Java. După cum ați aflat că există două grămezi: Min heap și Max heap, iată o diagramă:

Acum, trecând la următorul nostru segment, vom vedea cum să implementăm un heap binar în Java.

Cod:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Aceasta va inițializa heap-ul nostru cu dimensiunea implicită. * / public BinaryHeap (capacitate int) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Acest lucru va verifica dacă heap-ul este gol sau nu * Complexitate: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Aceasta va verifica dacă heap-ul este plin sau nu * Complexitate: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Acest lucru va insera element nou în heap * Complexitate: O (log N) * Ca scenariu cel mai rău caz, trebuie să traversăm până la rădăcină * / public void insert (int x) {if (isFull ()) aruncă o nouă NoSuchElementException ('Heap este plin, nu există spațiu de inserat element nou ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Acest lucru va șterge elementul la index x * Complexitate: O (jurnal N) * * / public int șterge (int x) {if (isEmpty ()) aruncă o nouă NoSuchElementException ('Heap este gol, nu există element de șters') int key = heap [x] heap [x] = heap [heapSize -1] heapSize - heapifyDown (x) retu cheie rn} / ** * Această metodă utilizată pentru a menține proprietatea heap în timp ce introduceți un element. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Această metodă utilizată pentru menținerea proprietății heap în timp ce ștergeți un element. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Această metodă utilizată pentru a imprima toate elementele heap-ului * * / public void printHeap () {System.out.print ('nHeap =') pentru (int i = 0 i
Cu aceasta, ajungem la sfârșitul acestui articol despre Binary Heap în Java. Verificați    de Edureka, o companie de învățare online de încredere, cu o rețea de peste 250.000 de elevi mulțumiți răspândiți pe tot globul. Cursul de formare și certificare Java J2EE și SOA al Edureka este conceput pentru studenți și profesioniști care doresc să fie dezvoltator Java. Cursul este conceput pentru a vă oferi un început avansat în programarea Java și pentru a vă instrui atât pentru conceptele Java de bază, cât și pentru cele avansate, împreună cu diverse cadre Java, cum ar fi Hibernate & Spring. 
 Ai o întrebare pentru noi? Vă rugăm să o menționați în secțiunea de comentarii a acestui blog „Java ArrayList” și vă vom contacta cât mai curând posibil.