what is heap data structure java
Denne veiledningen forklarer hva som er Java Heap-datastruktur og relaterte konsepter som Min Heap, Max Heap, Heap Sort, Stack vs Heap med eksempler:
En bunke er en spesiell datastruktur i Java. En haug er en trebasert datastruktur og kan klassifiseres som et komplett binært tre. Alle noder på haugen er ordnet i en bestemt rekkefølge.
=> Besøk her for å se Java Training Series for alle
Hva du vil lære:
Heap Datastruktur i Java
I haundatastrukturen sammenlignes rotnoden med sine barn og ordnes i henhold til rekkefølgen. Så hvis a er en rotnode og b er dens barn, så er eiendommen, nøkkel (a)> = nøkkel (b) vil generere en maks bunke.
Ovennevnte forhold mellom roten og undernoden kalles “Heap Property”.
Avhengig av rekkefølgen på foreldre-barn noder, er dyngen vanligvis av to typer:
# 1) Max-Heap :I en Max-Heap er rotnøkkelen den største av alle nøklene i dyngen. Det bør sikres at den samme egenskapen gjelder for alle undertrær i haugen rekursivt.
Diagrammet nedenfor viser en prøve Max Heap. Merk at rotnoden er større enn sine barn.
# 2) Min-Heap :Når det gjelder en Min-Heap, er rotnodenøkkelen den minste eller minimumet blant alle de andre nøklene som er tilstede i haugen. Som i Max heap, bør denne egenskapen være rekursivt sant i alle de andre undertrærne i bunken.
Et eksempel, av et Min-heap-tre, er vist nedenfor. Som vi kan se er rotnøkkelen den minste av alle de andre nøklene i dyngen.
En havedatastruktur kan brukes i følgende områder:
- Hauger brukes mest til å implementere prioritetskøer.
- Spesielt min-heap kan brukes til å bestemme de korteste banene mellom toppunktene i en graf.
Som allerede nevnt er havedatastrukturen et komplett binært tre som tilfredsstiller haugegenskapene for rot og barn. Denne haugen kalles også som en binær haug .
Binær haug
En binær bunke oppfyller nedenstående egenskaper:
- En binær haug er et komplett binært tre. I et komplett binært tre er alle nivåene unntatt det siste nivået fullstendig fylt. På siste nivå er tastene så langt som mulig igjen.
- Det tilfredsstiller haugegenskapen. Den binære bunken kan være maks eller min bunke, avhengig av heapegenskapen den tilfredsstiller.
En binær haug blir normalt representert som en matrise. Siden det er et komplett binært tre, kan det enkelt vises som en matrise. Dermed i en matrixrepresentasjon av binær dyng vil rotelementet være A [0] der A er matrisen som brukes til å representere den binære dyngen.
Så generelt for alle ithnode i den binære heap array-representasjonen, A [i], kan vi representere indeksene til andre noder som vist nedenfor.
A [(i-1) / 2] | Representerer foreldrenoden |
---|---|
Tilgangen går raskere. | Tregere enn stabelen. |
A [(2 * i) +1] | Representerer venstre barneknute |
A [(2 * i) +2] | Representerer riktig barneknute |
Tenk på følgende binære dyng:
Arrayrepresentasjonen av den ovennevnte min binære bunken er som følger:
Som vist ovenfor krysses dyngen i henhold til nivåordre dvs. elementene krysses fra venstre til høyre på hvert nivå. Når elementene på ett nivå er oppbrukt, går vi videre til neste nivå.
Deretter vil vi implementere den binære dyngen i Java.
Programmet nedenfor viser den binære dyngen i Java.
import java.util.*; class BinaryHeap { private static final int d= 2; private int[] heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int[ capacity+1]; Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap 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); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap[x]; heap[x] = heap[heapSize -1]; heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion 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; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap[i]; while(kthChild(i, 1) heap[rightChild]?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Produksjon:
nHeap = 7 4 6 1 3 2 5
Min haug i Java
En min-haug i Java er et komplett binært tre. I min-heap er rotnoden mindre enn alle andre noder i bunken. Generelt er nøkkelverdien til hver intern node mindre enn eller lik den underordnede noden.
Når det gjelder matrixrepresentasjon av min-heap, hvis en node er lagret i posisjon ‘i’, så er dens venstre undernode lagret i posisjon 2i + 1 og deretter er den høyre undernoden i posisjon 2i + 2. Posisjonen (i-1) / 2 returnerer sin overordnede node.
Nedenfor er de forskjellige operasjonene støttet av min-heap.
# 1) Sett inn (): Opprinnelig legges en ny nøkkel til på slutten av treet. Hvis nøkkelen er større enn den overordnede noden, opprettholdes heap-eiendommen. Ellers må vi krysse nøkkelen oppover for å oppfylle haugegenskapen. Innsettingsoperasjon i min bunke tar O (log n) tid.
# 2) extractMin (): Denne operasjonen fjerner minimumselementet fra dyngen. Merk at haugegenskapen skal opprettholdes etter at rotelementet (min-elementet) er fjernet fra dyngen. Hele denne operasjonen tar O (Logn).
# 3) getMin (): getMin () returnerer roten til dyngen som også er minimumselementet. Denne operasjonen utføres i O (1) tid.
Nedenfor er et eksempel på et tre for en Min-haug.
Ovenstående diagram viser et minhaugetre. Vi ser at roten til treet er minimumselementet i treet. Ettersom roten er på sted 0, plasseres venstre barn på 2 * 0 + 1 = 1 og høyre barn er på 2 * 0 + 2 = 2.
Min Heap Algorithm
Nedenfor er algoritmen for å bygge en min-haug.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A[ ] , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A[left] < A[ i ] ) smallest = left; else smallest = i; if(right <= N and A[right] < A[smallest] ) smallest = right; if(smallest != i) { swap A[ i ] and A[ smallest ]); call min_heapify (A, smallest,N); } }
Min haugimplementering i Java
Vi kan implementere min-bunken enten ved hjelp av array- eller prioritetskøer. Implementering av min-heap ved hjelp av prioritetskøer er standardimplementeringen ettersom en prioritert kø implementeres som min-heap.
Følgende Java-program implementerer min-haugen ved hjelp av Arrays. Her bruker vi matrixrepresentasjon for heap og bruker deretter heapify-funksjonen for å opprettholde heap-egenskapen til hvert element lagt til heapen. Til slutt viser vi dyngen.
class Min_Heap { private int[] HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int[this.maxsize + 1]; HeapArray[0] = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray[leftChild(pos)] || HeapArray[pos] > HeapArray[rightChild(pos)]) { // swap with left child and then heapify the left child if (HeapArray[leftChild(pos)] = maxsize) { return; } HeapArray[++size] = element; int current = size; while (HeapArray[current] = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray[FRONT]; HeapArray[FRONT] = HeapArray[size--]; minHeapify(FRONT); return popped; } } class Main{ public static void main(String[] arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } }
Produksjon:
Max Heap I Java
En maks bunke er også et komplett binært tre. I en maks bunke er rotnoden større enn eller lik barnets noder. Generelt er verdien av en hvilken som helst intern node i en maks bunke større enn eller lik dens undernoder.
Mens maks heap er kartlagt til en matrise, hvis noen node er lagret i posisjon ‘i’, blir det venstre barnet lagret på 2i +1 og det høyre barnet lagres på 2i + 2.
Typisk Max-heap vil se ut som vist nedenfor:
I diagrammet ovenfor ser vi at rotnoden er den største i dyngden, og dens undernoder har verdier mindre enn rotnoden.
I likhet med min-heap, kan max-heapen også vises som en matrise.
Så hvis A er en matrise som representerer Max heap, så er A [0] rotnoden. Tilsvarende, hvis A [i] er en hvilken som helst node i maks bunke, så er følgende de andre tilstøtende noder som kan vises med en matrise.
- A [(i-1) / 2] representerer foreldrenoden til A [i].
- A [(2i +1)] representerer venstre undernode til A [i].
- A [2i + 2] returnerer høyre underknutepunkt for A [i].
Operasjonene som kan utføres på Max Heap er gitt nedenfor.
# 1) Sett inn: Insert-operasjon setter inn en ny verdi i max heap-treet. Den settes inn på enden av treet. Hvis den nye nøkkelen (verdien) er mindre enn den overordnede noden, opprettholdes heap-eiendommen. Ellers må treet heapifiseres for å opprettholde haugegenskapen.
flvto vil ikke la meg konvertere
Tidskompleksiteten til innsatsoperasjonen er O (log n).
# 2) ExtractMax: Operasjonen ExtractMax fjerner det maksimale elementet (root) fra maks bunken. Operasjonen heapiserer også maks heap for å opprettholde haugegenskapen. Tidskompleksiteten til denne operasjonen er O (log n).
# 3) getMax: getMax-operasjonen returnerer rotnoden til maks bunken med tidskompleksiteten til O (1).
Java-programmet nedenfor implementerer maksimumsbunken. Vi bruker ArrayList her for å representere maks heap-elementene.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args[]) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } }
Produksjon:
Priority Queue Min Heap In Java
Prioriteringskodatastrukturen i Java kan brukes direkte til å representere min-haugen. Som standard implementerer prioritetskøen min-heap.
Programmet nedenfor viser min-haugen i Java ved hjelp av Priority Queue.
import java.util.*; class Main { public static void main(String args[]) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }
Produksjon:
Prioritetskø Maks haug i Java
For å representere maks heap i Java ved hjelp av Priority-køen, må vi bruke Collections.reverseOrder for å reversere min-heap. Prioritetskøen representerer direkte en min-haug i Java.
Vi har implementert Max Heap ved hjelp av en Priority-kø i programmet nedenfor.
import java.util.*; class Main { public static void main(String args[]) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }
Produksjon:
Haugsortering i Java
Haugsortering er en sammenligningssorteringsteknikk som ligner utvalgssortering der vi velger et maksimalt element i matrisen for hver iterasjon. Heap sort bruker Heap datastruktur og sorterer elementene ved å lage min eller max heap ut av arrayelementene som skal sorteres.
Vi har allerede diskutert at rotnoden inneholder minimums- og maksimumselement i henholdsvis min og maks heap. I happesortering fjernes rotelementet til haugen (min eller maks) og flyttes til den sorterte matrisen. Den gjenværende haugen blir deretter heapifisert for å opprettholde haugegenskapen.
Så vi må utføre to trinn rekursivt for å sortere den gitte matrisen ved hjelp av haugsortering.
- Bygg en haug fra den gitte matrisen.
- Fjern rotelementet gjentatte ganger fra haugen og flytt det til den sorterte matrisen. Heapify den gjenværende bunken.
Time Complexity of Heap sort er O (n log n) i alle tilfeller. Romkompleksiteten er O (1).
Haugsorteringsalgoritme i Java
Nedenfor er høysorteringsalgoritmene for å sortere den gitte matrisen i stigende og synkende rekkefølge.
# 1) Heap Sorteringsalgoritme for å sortere i stigende rekkefølge:
- Lag en maksimal heap for den gitte matrisen som skal sorteres.
- Slett roten (maksimumsverdi i inngangsruten) og flytt den til den sorterte matrisen. Plasser det siste elementet i matrisen ved roten.
- Heapify den nye roten til dyngen.
- Gjenta trinn 1 og 2 til hele matrisen er sortert.
# 2) Heap Sorteringsalgoritme for å sortere i synkende rekkefølge:
- Konstruer en min haug for den gitte matrisen.
- Fjern roten (minimumsverdi i matrisen) og bytt den med det siste elementet i matrisen.
- Heapify den nye roten til dyngen.
- Gjenta trinn 1 og 2 til hele matrisen er sortert.
Heap Sort Implementation In Java
Java-programmet nedenfor bruker heap sort for å sortere en matrise i stigende rekkefølge. For dette konstruerer vi først en maks heap og deretter rekursivt bytter og heapify rotelementet som spesifisert i algoritmen ovenfor.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array[]) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array[0]; heap_Array[0] = heap_Array[i]; heap_Array[i] = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array[], int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array[largest]) largest = left; if (right heap_Array[largest]) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array[i]; heap_Array[i] = heap_Array[largest]; heap_Array[largest] = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args[]) { //define input array and print it int heap_Array[] = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } }
Produksjon:
Den samlede tidskompleksiteten til haugsorteringsteknikken er O (nlogn). Tidskompleksiteten til heapify-teknikken er O (logn). Mens tidskompleksiteten til å bygge dyngen er O (n).
Stack Vs Heap I Java
La oss nå tabellisere noen av forskjellene mellom en Stack-datastruktur og en heap.
Stable Haug En stabel er en lineær datastruktur. En bunke er en hierarkisk datastruktur. Følger bestilling av LIFO (Last In, First Out). Gjennomgang er i jevn rekkefølge. Brukes mest for statisk minnetildeling. Brukes til dynamisk minnetildeling. Minne tildeles sammenhengende. Minne tildeles på tilfeldige steder. Stakkstørrelsen er begrenset i henhold til operativsystemet. Ingen grense for haugstørrelse håndhevet av operativsystemet. Stack har bare tilgang til lokale variabler. Heap har globale variabler tildelt. Allokering / avdeling av minne er automatisk. Tildeling / deallocation må gjøres manuelt av programmereren. Stakken kan implementeres ved hjelp av Arrays, Linked List, ArrayList, etc. eller andre lineære datastrukturer. Heap implementeres ved hjelp av Arrays eller trær. Vedlikeholdskostnader hvis mindre. Dyrere å vedlikeholde. Kan føre til mangel på minne da minnet er begrenset. Ingen mangel på minne, men kan lide av minnefragmentering.
ofte stilte spørsmål
Q # 1) Er stack raskere enn Heap?
Svar: En bunke er raskere enn dyngen da tilgang er lineær i stabelen sammenlignet med dyngen.
Q # 2) Hva brukes en haug til?
Svar: Heap brukes for det meste i algoritmer som finner den minste eller korteste stien mellom to punkter som Dijkstras algoritme, for å sortere ved hjelp av haugsortering, for prioritering av køimplementeringer (min-haug) osv.
Q # 3) Hva er en haug? Hva er typene?
Svar: En haug er en hierarkisk, trebasert datastruktur. En haug er et komplett binært tre. Heaps er av to typer, dvs. Max heap der rotnoden er den største blant alle nodene; Min heap der rotnoden er det minste eller minimumet blant alle tastene.
Sp # 4) Hva er fordelene med Heap fremfor en bunke?
Svar: Den største fordelen med bunken i forhold til stakken er i bunken, minnet tildeles dynamisk, og det er derfor ingen grense for hvor mye minne som kan brukes. For det andre kan bare lokale variabler tildeles på bunken mens vi også kan tildele globale variabler på bunken.
Sp # 5) Kan Heap ha duplikater?
Svar: Ja, det er ingen begrensninger for å ha noder med dupliserte nøkler i bunken, da bunken er et komplett binært tre, og det tilfredsstiller ikke egenskapene til det binære søketreet.
Konklusjon
I denne opplæringen har vi diskutert typer heap og heap sorter ved hjelp av typer heap. Vi har også sett den detaljerte implementeringen av typene i Java.
=> Ta en titt på den perfekte Java-treningsguiden her.
Anbefalt lesing
- Java Graph Tutorial - Hvordan implementere grafdatastruktur
- Introduksjon til datastrukturer i C ++
- Haugsortering i C ++ med eksempler
- AVL Tree and Heap Datastruktur i C ++
- Datastruktur for binært tre i C ++
- Kødatastruktur i C ++ med illustrasjon
- Sirkulær koblet liste Datastruktur i C ++ med illustrasjon
- Java Basics: Java Syntax, Java Class og Core Java Concepts