Förstå hur man implementerar en binär hög i Java

Den här artikeln ger dig en fullständig översikt över hur sorteringen fungerar och senare lär vi oss att implementera en binär hög i Java.

Här är dagordningen för denna artikel:

c ++ goto uttalande

1. Vad är högsortering?
2. Max Heap
3. Min hög
4. Heapimplementering i Java
   • Diagram
   • Koda

Låt oss börja!

Vad är högsortering?

Heap är i grunden en trädbaserad datastruktur. Den har noder. Noden består av vissa element. Varje nod innehåller ett element.

Noder kan ha barn. Om det inte finns några barn kallas det ett blad.

Det finns två regler som ska följas:

• Värdet på varje nod måste vara mindre eller lika med alla värden som lagras i dess underordnade.
• Den har minst möjlig höjd.

Högar är extremt effektiva för att extraheraminst eller största element.

Låt oss gå vidare till min hög nu!

Min hög

Min heap är ett komplett binärt träd där rotelementets värde är mindre än eller lika med något av underelementet.

Representation av min hög

Arr [(i-1) / 2]: detta returnerar föräldernoden.

Arr [(2 * i) + 1]: detta returnerar den vänstra barnnoden.

Arr [(2 * i) + 2]: detta kommer att returnera rätt barnnod.

Det finns vissa metoder för Min Heap:

• Föra in(): En ny nyckel i slutet av trädet läggs till. Om den nya nyckeln är större än föräldern, behöver du inte göra någonting, annars måste vi gå igenom för att ställa in heapegenskapen.
• getMin (): de här metoderna hjälper till att returnera rotelementet.
• extractMin (): den här metoden returnerar lägstaelement.

Gå vidare till Max heap nu.

Max hög

Max heap är ett komplett binärt träd där rotelementets värde är större än eller lika med något av underelementet.

vår mvc handledning för nybörjare

Max heap består av flera metoder också!

• Föra in (): det kommer att infoga ett element i högen.
• Radera() : det tar bort ett element från högen.
• FindMax (): den hittar det maximala elementet från högen.
• printHeap (): Det kommer att skriva ut innehållet på högen

Låt mig nu visa implementeringen av heap genom ett diagram och senare ett Javakoda.

Heapimplementering i Java

Diagram:

Diagrammet ovan visar den binära högen i Java. Som du har lärt dig att det finns två högar: Min hög och Max hög, här är ett diagram:

omfångsupplösningsoperatör c ++

Nu, när vi går vidare till vårt nästa segment, kommer vi att se hur man implementerar en binär hög i Java.

Koda:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Detta initialiserar vår heap med standardstorlek. * / public BinaryHeap (int-kapacitet) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Detta kontrollerar om högen är tom eller inte * Komplexitet: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Detta kontrollerar om heapen är full eller inte * Komplexitet: O (1) * / public boolean isFull () {return heapSize == heap .längd} privat int förälder (int i) {retur (i-1) / d} privat int kthChild (int i, int k) {return d * i + k} / ** * Detta infogar nytt element i att heap * Komplexitet: O (log N) * I värsta fall måste vi korsa till roten * / public void insert (int x) {if (isFull ()) kasta nytt NoSuchElementException ('Heap is full, No space to insert nytt element ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Detta raderar element vid index x * Komplexitet: O (log N) * * / public int delete (int x) {if (isEmpty ()) kasta nytt NoSuchElementException ('Heap är tomt, inget element att radera') int-tangent = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn-tangent} / ** * Denna metod används för att bibehålla heap-egenskapen när du sätter in ett element. * * / privat ogiltigt heapifyUp (int i) {int temp = heap [i] medan (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Denna metod används för att bibehålla heap-egenskapen medan du tar bort ett element. * * / privat ogiltigt heapifyDown (int i) {int barn int temp = heap [i] medan (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Denna metod används för att skriva ut alla element i heapen * * / public void printHeap () {System.out.print ('nHeap =') för (int i = 0 i
Med detta kommer vi till ett slut på den här artikeln om Binary Heap i Java. Kolla in    av Edureka, ett pålitligt inlärningsföretag online med ett nätverk av mer än 250 000 nöjda elever spridda över hela världen. Edurekas Java J2EE- och SOA-utbildning och certifieringskurs är utformad för studenter och yrkesverksamma som vill vara Java-utvecklare. Kursen är utformad för att ge dig ett försprång till Java-programmering och träna dig för både kärn- och avancerade Java-koncept tillsammans med olika Java-ramverk som Hibernate & Spring. 
 Har du en fråga till oss? Vänligen nämna det i kommentarsektionen i denna “Java ArrayList” -blogg så återkommer vi till dig så snart som möjligt.