Forstå, hvordan du implementerer en binær bunke i Java



Denne artikel vil give dig en detaljeret og omfattende kendskab til, hvordan du hindrer en binær bunke i java med eksempler.

Denne artikel giver dig et komplet overblik over bearbejdningen af ​​dyngsortering, og senere lærer vi at implementere en binær bunke i Java.

Her er dagsordenen for denne artikel:





  1. Hvad er bunksortering?
  2. Max Heap
  3. Min bunke
  4. Heap-implementering i Java
    • Diagram
    • Kode

Lad os begynde!

Hvad er bunksortering?

Heap er dybest set en træbaseret datastruktur. Det har knudepunkter. Node består af visse elementer. Hver knude indeholder et element.



Knuder kan have børn. Hvis der ikke er nogen børn, kaldes det et blad.

Der er to regler, der skal følges:

  • Værdien af ​​hver node skal være mindre eller lig med alle de værdier, der er gemt i dens børn.
  • Det har den mindst mulige højde.

Hauger er ekstremt effektive til at udvindemindst eller største element.



Lad os gå videre til min bunke nu!

Min bunke

Min bunke er et komplet binært træ, hvor værdien af ​​rodelementet er mindre end eller lig med et af underelementet.

Repræsentation af min bunke

Arr [(i-1) / 2]: dette returnerer den overordnede knude.

Arr [(2 * i) + 1]: dette vil returnere venstre barneknude.

Arr [(2 * i) + 2]: dette vil returnere den rigtige barneknude.

Der er visse metoder til Min Heap:

  • indsæt (): En ny nøgle i slutningen af ​​træet tilføjes. Hvis den nye nøgle er større end forælderen, er der ikke behov for at gøre noget, ellers er vi nødt til at krydse op for at oprette bunkeegenskaben.
  • getMin (): disse metoder hjælper med at returnere rodelementet.
  • extractMin (): denne metode returnerer minimumetelement.

Gå videre til Max bunke nu.

Max bunke

Max heap er et komplet binært træ, hvor værdien af ​​rodelementet er større end eller lig med et af underelementet.

Max heap består også af flere metoder!

  • Indsæt (): det indsætter et element i bunken.
  • Slet () : det sletter et element fra bunken.
  • FindMax (): det finder det maksimale element fra bunken.
  • printHeap (): Det udskriver bunkenes indhold

Lad mig nu vise dig bunkeimplementeringen gennem et diagram og senere en Javakode.

Heap-implementering i Java

Diagram:

Heap

Diagrammet ovenfor viser den binære bunke i Java. Som du har lært, at der er to dynger: Min bunke og Max bunke, her er et diagram:

Når vi går videre til vores næste segment, vil vi se, hvordan vi implementerer en binær bunke i Java.

Kode:

offentlig klasse BinaryHeap {privat statisk endelig int d = 2 privat int [] heap privat int heapSize / ** * Dette initialiserer vores bunke med standardstørrelse. * / public BinaryHeap (int-kapacitet) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Dette vil kontrollere, om bunken er tom eller ikke * Kompleksitet: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Dette kontrollerer, om bunken er fuld eller ej * Kompleksitet: O (1) * / public boolean isFull () {return heapSize == heap .længde} privat int forælder (int i) {return (i-1) / d} privat int kthChild (int i, int k) {return d * i + k} / ** * Dette indsætter nyt element i for at bunke * Kompleksitet: O (log N) * I værste fald skal vi krydse indtil roden * / public void insert (int x) {if (isFull ()) smide nyt NoSuchElementException ('Heap is full, No space to insert nyt element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Dette sletter element ved indeks x * Kompleksitet: O (log N) * * / public int delete (int x) {if (isEmpty ()) smid nyt NoSuchElementException ('Heap er tom, intet element at slette') int-nøgle = heap [x] heap [x] = heap [heapSize -1] heapSize - heapifyDown (x) retu rn-nøgle} / ** * Denne metode bruges til at opretholde heap-egenskaben, mens du indsætter et element. * * / privat ugyldigt 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} / ** * Denne metode bruges til at vedligeholde heap-egenskaben, mens et element slettes. * * / privat ugyldigt heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Denne metode bruges til at udskrive alle elementerne i bunken * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i

Med dette kommer vi til slutningen af ​​denne artikel om Binary Heap i Java. Tjek den af Edureka, et pålideligt online læringsfirma med et netværk på mere end 250.000 tilfredse elever spredt over hele kloden. Edurekas Java J2EE- og SOA-uddannelses- og certificeringskursus er designet til studerende og fagfolk, der ønsker at være Java-udvikler. Kurset er designet til at give dig et forspring i Java-programmering og træne dig til både kerne- og avancerede Java-koncepter sammen med forskellige Java-rammer som Hibernate & Spring.

Har du et spørgsmål til os? Nævn det i kommentarfeltet på denne “Java ArrayList” -blog, og vi vender tilbage til dig hurtigst muligt.

opsætning af formørkelse til java