Begrijp hoe u een binaire heap in Java implementeert



Dit artikel zal je voorzien van een gedetailleerde en uitgebreide kennis van hoe je een binaire heap in Java kunt impementeren met voorbeelden.

Dit artikel geeft je een compleet overzicht van de werking van heap sort en later zullen we leren om een ​​binaire hoop in Java te implementeren.

Hier is de agenda voor dit artikel:





  1. Wat is heap-sortering?
  2. Max. Hoop
  3. Min. Hoop
  4. Heap-implementatie in Java
    • Diagram
    • Code

Laten we beginnen!

Wat is heap-sortering?

Heap is in feite een boomgebaseerde datastructuur. Het heeft knooppunten. Knooppunt bestaat uit bepaalde elementen. Elk knooppunt bevat één element.



Knooppunten kunnen kinderen krijgen. Als er geen kinderen zijn, wordt het een blad genoemd.

Er zijn twee regels die moeten worden gevolgd:

  • De waarde van elk knooppunt moet kleiner zijn dan of gelijk zijn aan alle waarden die zijn opgeslagen in de onderliggende items.
  • Het heeft de kleinst mogelijke hoogte.

Heaps zijn buitengewoon efficiënt in het extraheren van deminste of grootste element.



Laten we nu verder gaan met min heap!

Min. Hoop

Min heap is een complete binaire boom waarin de waarde van het root-element kleiner is dan of gelijk is aan een van de onderliggende elementen.

Vertegenwoordiging van min heap

Arr [(i-1) / 2]: dit zal het bovenliggende knooppunt teruggeven.

Arr [(2 * i) + 1]: dit zal het linker onderliggende knooppunt teruggeven.

Arr [(2 * i) + 2]: dit zal het rechter onderliggende knooppunt teruggeven.

Er zijn bepaalde methoden van Min Heap:

  • invoegen (): Een nieuwe sleutel aan het einde van de boom wordt toegevoegd. Als de nieuwe sleutel groter is dan de ouder, hoeft u niets te doen, anders moeten we naar boven om de heap-eigenschap in te stellen.
  • getMin (): deze methode helpt om het root-element terug te geven.
  • extractMin (): deze methode geeft het minimum terugelement.

Ga nu verder met Max heap.

Max. Hoop

Max heap is een complete binaire boom waarin de waarde van het root-element groter is dan of gelijk is aan een van de onderliggende elementen.

Max heap bestaat ook uit verschillende methoden!

  • Invoegen (): het zal een element in de heap invoegen.
  • Verwijderen () : het zal een element uit de heap verwijderen.
  • FindMax (): het zal het maximale element uit de hoop vinden.
  • printHeap (): Het zal de inhoud van de hoop afdrukken

Laat me je nu de heap-implementatie laten zien door middel van een diagram en later een Javacode.

Heap-implementatie in Java

Diagram:

Heap

Het bovenstaande diagram toont de binaire heap in Java. Zoals je hebt geleerd, zijn er twee hopen: Min heap en Max heap, hier is een diagram:

Nu we verder gaan met ons volgende segment, zullen we zien hoe we een binaire heap in Java kunnen implementeren.

c ++ ga naar regel

Code:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Dit zal onze heap initialiseren met de standaardgrootte. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Dit zal controleren of de heap leeg is of niet * Complexiteit: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Dit zal controleren of de heap vol is of niet * Complexiteit: 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} / ** * Dit zal een nieuw element in de heap invoegen * Complexiteit: O (log N) * In het ergste geval moeten we doorlopen tot de root * / 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)} / ** * Dit verwijdert element op index x * Complexiteit: O (log N) * * / public int delete (int x) {if (isEmpty ()) throw nieuwe NoSuchElementException ('Heap is leeg, geen element om te verwijderen') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Deze methode wordt gebruikt om de heap-eigenschap te behouden tijdens het invoegen van een element. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = ouder (i)} heap [i] = temp} / ** * Deze methode wordt gebruikt om de eigenschap heap te behouden tijdens het verwijderen van een element. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Deze methode wordt gebruikt om alle elementen van de heap * * / public void printHeap () {System.out.print ('nHeap =') af te drukken voor (int i = 0 i

Hiermee komen we aan het einde van dit artikel over Binary Heap in Java. Bekijk de door Edureka, een vertrouwd online leerbedrijf met een netwerk van meer dan 250.000 tevreden leerlingen verspreid over de hele wereld. De training- en certificeringcursus Java J2EE en SOA van Edureka is bedoeld voor studenten en professionals die Java Developer willen worden. De cursus is bedoeld om u een voorsprong te geven in het programmeren van Java en u te trainen in zowel kern- als geavanceerde Java-concepten, samen met verschillende Java-frameworks zoals Hibernate & Spring.

Heeft u een vraag voor ons? Vermeld het in het commentaargedeelte van deze 'Java ArrayList' -blog en we nemen zo snel mogelijk contact met u op.