Forstå hvordan du implementerer en binær haug i Java

Denne artikkelen vil gi deg en fullstendig oversikt over bearbeiding av haugsortering, og senere vil vi lære å implementere en binær haug i Java.

Her er agendaen for denne artikkelen:

1. Hva er haugsortering?
2. Max Heap
3. Min haug
4. Heap implementering i Java
   • Diagram
   • Kode

La oss begynne!

Hva er haugsortering?

Heap er i utgangspunktet en trebasert datastruktur. Den har noder. Node består av visse elementer. Hver node inneholder ett element.

Noder kan ha barn. Hvis det ikke er barn, kalles det et blad.

Det er to regler som skal følges:

• Verdien til hver node må være mindre eller lik alle verdiene som er lagret i sine barn.
• Den har minst mulig høyde.

Hauger er ekstremt effektive i å utvinneminste eller største element.

La oss gå videre til min heap nå!

system.exit (0)

Min haug

Min heap er et komplett binært tre der verdien av rotelementet er mindre enn eller lik et av underelementet.

Representasjon av min haug

Arr [(i-1) / 2]: dette vil returnere foreldrenoden.

Arr [(2 * i) + 1]: Dette vil returnere venstre barneknute.

Arr [(2 * i) + 2]: Dette vil returnere den rette barnekoden.

Det er visse metoder for Min Heap:

• sett inn(): En ny nøkkel på slutten av treet er lagt til. Hvis den nye nøkkelen er større enn den overordnede, er det ikke nødvendig å gjøre noe, ellers må vi krysse opp for å sette opp haugegenskapen.
• getMin (): disse metodene hjelper til med å returnere rotelementet.
• extractMin (): denne metoden returnerer minimumelement.

Gå videre til Max heap nå.

Maks haug

Max heap er et komplett binært tre der verdien av rotelementet er større enn eller lik et av underelementet.

Max heap består av flere metoder også!

• Sett inn (): det vil sette inn et element i dyngen.
• Slett () : det vil slette et element fra dyngen.
• FindMax (): det vil finne det maksimale elementet fra dyngen.
• printHeap (): Det vil skrive ut innholdet på dyngen

La meg nå vise deg haugimplementeringen gjennom et diagram og senere en Javakode.

Heap implementering i Java

Diagram:

hvordan du avslutter programmet java

Diagrammet over viser den binære dyngen i Java. Som du har lært at det er to dynger: Min heap og Max heap, her er et diagram:

Nå, videre til vårt neste segment, vil vi se hvordan vi implementerer en binær haug i Java.

Kode:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Dette vil initialisere bunken vår med standardstørrelse. * / offentlig BinaryHeap (int kapasitet) {heapSize = 0 heap = new int [kapasitet + 1] Arrays.fill (heap, -1)} / ** * Dette vil sjekke om bunken er tom eller ikke * Kompleksitet: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Dette vil sjekke om bunken er full eller ikke * Kompleksitet: O (1) * / public boolean isFull () {return heapSize == heap .length} private int foreldre (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Dette vil sette inn nytt element i for å heap * Kompleksitet: O (logg N) * I verste fall må vi krysse til roten * / public void insert (int x) {if (isFull ()) throw new NoSuchElementException ('Heap is full, No space to insert nytt element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Dette vil slette elementet ved indeks x * Kompleksitet: O (log N) * * / public int delete (int x) {if (isEmpty ()) kast nytt NoSuchElementException ('Heap is empty, No element to delete') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Denne metoden brukes til å opprettholde heap-egenskapen mens du setter inn et element. * * / privat ugyldig 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 metoden brukes til å opprettholde heap-egenskapen mens du sletter et element. * * / privat ugyldig heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Denne metoden brukes til å skrive ut alle elementene i bunken * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i
Med dette kommer vi til en slutt på denne artikkelen om Binary Heap in Java. Sjekk ut    av Edureka, et pålitelig online læringsfirma med et nettverk av mer enn 250 000 fornøyde elever spredt over hele verden. Edurekas Java J2EE- og SOA-opplæring og sertifiseringskurs er designet for studenter og fagpersoner som ønsker å være Java-utvikler. Kurset er designet for å gi deg et forsprang i Java-programmering og trene deg for både kjerne- og avanserte Java-konsepter sammen med forskjellige Java-rammer som Hibernate & Spring. 
 Har du et spørsmål til oss? Vennligst nevn det i kommentarfeltet i denne 'Java ArrayList' -bloggen, så kommer vi tilbake til deg så snart som mulig.