Menu

Hvad er en bunke datastruktur i Java

what is heap data structure java

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning forklarer, hvad der er Java Heap-datastruktur og relaterede begreber som Min Heap, Max Heap, Heap Sort, Stack vs Heap med eksempler:

En bunke er en speciel datastruktur i Java. En bunke er en træbaseret datastruktur og kan klassificeres som et komplet binært træ. Alle knudepunkterne på bunken er arrangeret i en bestemt rækkefølge.

=> Besøg her for at se Java Training Series for alle

Heap-datastruktur

Hvad du vil lære:

Heap-datastruktur i Java

I bunke-datastrukturen sammenlignes rodnoden med dens børn og arrangeres efter rækkefølgen. Så hvis a er en rodknude og b er dens barn, så er ejendommen, nøgle (a)> = nøgle (b) genererer en maksimal bunke.

Ovenstående forhold mellem roden og underknudepunktet kaldes “Heap Property”.

Afhængigt af rækkefølgen af ​​forældre-barn noder er bunken generelt af to typer:

# 1) Max-Heap :I en Max-Heap er rodnodenøglen den største af alle nøglerne i bunken. Det skal sikres, at den samme egenskab gælder for alle undertrær i bunken rekursivt.

Nedenstående diagram viser en prøve maks. Bunke. Bemærk, at rodnoden er større end dens børn.

Prøve på Max-Heap

# 2) Min-bunke :I tilfælde af en Min-Heap er rodnodenøglen den mindste eller mindst blandt alle de andre nøgler, der findes i bunken. Som i Max bunke, skal denne egenskab være rekursivt sand i alle de andre undertrær i bunken.

Et eksempel, af et Min-bunketræ, er vist nedenfor. Som vi kan se, er rodnøglen den mindste af alle de andre nøgler i bunken.

Min-Heap træ

En bunke-datastruktur kan bruges i følgende områder:

  • Bunke bruges mest til at implementere prioritetskøer.
  • Især min-bunke kan bruges til at bestemme de korteste stier mellem hjørnerne i en graf.

Som allerede nævnt er bunke-datastrukturen et komplet binært træ, der tilfredsstiller heap-egenskaben for root og børnene. Denne bunke kaldes også som en binær bunke .

Binær bunke

En binær bunke opfylder nedenstående egenskaber:

  • En binær bunke er et komplet binært træ. I et komplet binært træ er alle niveauer undtagen det sidste niveau fuldstændigt udfyldt. På det sidste niveau er tasterne så langt tilbage som muligt.
  • Det tilfredsstiller bunkejendom. Den binære bunke kan være maks eller min bunke afhængigt af den bunkeegenskab, den opfylder.

En binær bunke er normalt repræsenteret som en matrix. Da det er et komplet binært træ, kan det let repræsenteres som et array. I en matrixrepræsentation af binær bunke vil rodelementet således være A [0], hvor A er det array, der bruges til at repræsentere den binære bunke.

Så generelt for enhver ithnode i den binære heap-array-repræsentation, A [i], kan vi repræsentere indekserne for andre noder som vist nedenfor.

A [(i-1) / 2]Repræsenterer den overordnede knude
Adgangen er hurtigere.Langsommere end stakken.
A [(2 * i) +1]Repræsenterer venstre barneknude
A [(2 * i) +2]Repræsenterer den rigtige underknude

Overvej følgende binære bunke:

binær bunke

Arrayrepræsentationen af ​​ovenstående min binære bunke er som følger:

matrixrepræsentation - Min binær bunke

Som vist ovenfor krydses dyngen i henhold til niveau rækkefølge dvs. elementerne krydses fra venstre mod højre på hvert niveau. Når elementerne på et niveau er opbrugt, går vi videre til det næste niveau.

Dernæst implementerer vi den binære bunke i Java.

Nedenstående program viser den binære bunke 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

Produktion:

nHeap = 7 4 6 1 3 2 5

Min bunke i Java

En min-bunke i Java er et komplet binært træ. I min-bunke er rodnoden mindre end alle de andre noder i bunken. Generelt er nøgleværdien for hver intern node mindre end eller lig med dens underordnede noder.

For så vidt angår array-repræsentation af min-bunke, hvis en node er lagret i position 'i', så er dens venstre underknude lagret i position 2i + 1, og derefter er den højre underknude i position 2i + 2. Positionen (i-1) / 2 returnerer sin overordnede node.

Nedenfor er de forskellige operationer understøttet af min-bunke.

# 1) Indsæt (): Oprindeligt tilføjes en ny nøgle i slutningen af ​​træet. Hvis nøglen er større end dens overordnede knudepunkt, opretholdes bunkeegenskaben. Ellers er vi nødt til at krydse nøglen opad for at opfylde bunkeegenskaben. Indsættelse i min bunke tager O (log n) tid.

# 2) extractMin (): Denne handling fjerner minimumselementet fra bunken. Bemærk, at egenskaben heap skal opretholdes, efter at rodelementet (min. Element) er fjernet fra bunken. Hele denne operation tager O (Logn).

# 3) getMin (): getMin () returnerer roden af ​​bunken, som også er minimumselementet. Denne operation udføres i O (1) tid.

Nedenfor er et eksempel på et træ til en Min-bunke.

Eksempel på Min-bunke

Ovenstående diagram viser et min-bunke-træ. Vi ser, at træets rod er minimumselementet i træet. Da roden er på placering 0, placeres dens venstre barn på 2 * 0 + 1 = 1, og højre barn er på 2 * 0 + 2 = 2.

Min Heap Algorithm

Nedenfor er algoritmen til opbygning af en min-bunke.

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 bunkeimplementering i Java

Vi kan implementere min-bunken enten ved hjælp af array- eller prioritetskøer. Implementering af min-heap ved hjælp af prioritetskøer er standardimplementeringen, da en prioritetskø implementeres som min-heap.

Følgende Java-program implementerer min-bunken ved hjælp af Arrays. Her bruger vi matrixrepræsentation for heap og anvender derefter heapify-funktionen for at opretholde heap-egenskaben for hvert element, der føjes til bunken. Endelig viser vi bunken.

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()); } }

Produktion:

Min bunkeimplementering i Java

Max Heap I Java

En maksimal bunke er også et komplet binært træ. I en maksimal bunke er rodnoden større end eller lig med underknudepunkterne. Generelt er værdien af ​​enhver intern node i en maksimal bunke større end eller lig med dens underordnede noder.

Mens maks. Heap er kortlagt til en matrix, hvis en node er gemt i position 'i', gemmes dens venstre barn ved 2i +1, og det højre barn lagres ved 2i + 2.

Typisk Max-heap ser ud som vist nedenfor:

Maks bunke i Java

I ovenstående diagram ser vi, at rodnoden er den største i bunke, og dens underordnede noder har værdier, der er mindre end rodnoden.

Svarende til min-bunke, kan den maksimale bunke også repræsenteres som en matrix.

Så hvis A er et array, der repræsenterer Max heap, så er A [0] rodnoden. Tilsvarende, hvis A [i] er en hvilken som helst node i den maksimale bunke, så er følgende de andre tilstødende noder, der kan repræsenteres ved hjælp af en matrix.

  • A [(i-1) / 2] repræsenterer moderknudepunktet for A [i].
  • A [(2i +1)] repræsenterer den venstre underknude i A [i].
  • A [2i + 2] returnerer den højre underknudepunkt for A [i].

De operationer, der kan udføres på Max Heap, er angivet nedenfor.

# 1) Indsæt: Indsæt operation indsætter en ny værdi i det maksimale bunke-træ. Det indsættes i slutningen af ​​træet. Hvis den nye nøgle (værdi) er mindre end dens overordnede knude, opretholdes heap-ejendommen. Ellers skal træet heapificeres for at opretholde bunkeegenskaben.

bedste steder at se anime kaldet

Tidskompleksiteten af ​​indsatsoperationen er O (log n).

# 2) ExtractMax: Operationen ExtractMax fjerner det maksimale element (rod) fra den maksimale bunke. Operationen heapificerer også den maksimale bunke for at vedligeholde bunkeegenskaben. Tidenes kompleksitet for denne operation er O (log n).

# 3) getMax: getMax-operation returnerer rodknudepunktet for den maksimale bunke med tidskompleksiteten af ​​O (1).

Nedenstående Java-program implementerer den maksimale bunke. Vi bruger ArrayList her til at repræsentere de maksimale bunkeelementer.

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); } }

Produktion:

OUTPUT - Max Heap i Java

Prioritetskø Min bunke i Java

Datastrukturen for prioritetskø i Java kan bruges direkte til at repræsentere min-bunken. Som standard implementerer prioritetskøen min-bunke.

Nedenstående program demonstrerer min-bunken i Java ved hjælp af 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() + ' '); } }

Produktion:

OUTPUT - Prioritetskø Min bunke i Java

Prioritetskø maks. Bunke i Java

For at repræsentere den maksimale bunke i Java ved hjælp af Priority-køen skal vi bruge Collections.reverseOrder til at vende min-bunken. Prioritetskøen repræsenterer direkte en min-bunke i Java.

Vi har implementeret Max Heap ved hjælp af en prioritetskø i nedenstående program.

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() + ' '); } }

Produktion:

Max Heap Priority Queue

Heap Sort i Java

Heapsortering er en sammenligningssorteringsteknik svarende til selektionssortering, hvor vi vælger et maksimalt element i arrayet for hver iteration. Heap-sortering bruger Heap-datastruktur og sorterer elementerne ved at oprette min eller max-heap ud af de array-elementer, der skal sorteres.

Vi har allerede diskuteret, at rodminen i min og max heap indeholder minimums- og maksimumselementet i arrayet. I heap-sortering fjernes bunns rodelement (min eller max) og flyttes til det sorterede array. Den resterende bunke heapificeres derefter for at vedligeholde bunkeegenskaben.

Så vi er nødt til at udføre to trin rekursivt for at sortere det givne array ved hjælp af heap sort.

  • Byg en bunke fra det givne array.
  • Fjern rodelementet gentagne gange fra bunken, og flyt det til det sorterede array. Heapify den resterende bunke.

Tidskompleksitet af bunksortering er O (n log n) i alle tilfælde. Rumkompleksiteten er O (1).

Heap Sort Algorithm In Java

Nedenfor er de store sorteringsalgoritmer til at sortere det givne array i stigende og faldende rækkefølge.

# 1) Heap Sort-algoritme, der skal sorteres i stigende rækkefølge:

  • Opret en maksimal bunke for det givne array, der skal sorteres.
  • Slet roden (maksimumværdi i inputmatrixen), og flyt den til det sorterede array. Placer det sidste element i arrayet ved roden.
  • Heapify den nye rod af bunken.
  • Gentag trin 1 og 2, indtil hele arrayet er sorteret.

# 2) Heap Sort-algoritme, der skal sorteres i faldende rækkefølge:

  • Konstruer en min bunke til det givne array.
  • Fjern roden (minimumsværdi i arrayet) og skift den med det sidste element i arrayet.
  • Heapify den nye rod af bunken.
  • Gentag trin 1 og 2, indtil hele arrayet er sorteret.

Implementering af heapsortering i Java

Nedenstående Java-program bruger heap-sortering til at sortere en matrix i stigende rækkefølge. Til dette konstruerer vi først en maksimal bunke og bytter derefter rekursivt og heapificerer rodelementet som specificeret i ovenstående algoritme.

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)); } }

Produktion:

output - Heap Sort Implementation i Java

Den samlede tidskompleksitet af bunksorteringsteknikken er O (nlogn). Tidskompleksiteten af ​​heapify-teknikken er O (logn). Mens tidskompleksiteten ved at bygge bunken er O (n).

Stak mod bunke i Java

Lad os nu tabulere nogle af forskellene mellem en Stack-datastruktur og en bunke.

StakBunke
En stak er en lineær datastruktur.En bunke er en hierarkisk datastruktur.
Følger bestilling af LIFO (Last In, First Out).Traversal er i niveau rækkefølge.
Bruges mest til statisk hukommelsesallokering.Bruges til dynamisk hukommelsestildeling.
Hukommelse tildeles sammenhængende.Hukommelse allokeres tilfældigt.
Stakstørrelsen er begrænset i henhold til operativsystemet.Ingen begrænsning af bunke størrelse håndhævet af operativsystemet.
Stack har kun adgang til lokale variabler.Heap har globale variabler tildelt.
Tildelingen / deallokationen af ​​hukommelsen sker automatisk.Tildeling / deallocation skal udføres manuelt af programmøren.
Stakken kan implementeres ved hjælp af Arrays, Linked List, ArrayList osv. Eller andre lineære datastrukturer.Heap implementeres ved hjælp af Arrays eller træer.
Omkostninger til vedligeholdelse, hvis mindre.Dyrere at vedligeholde.
Kan resultere i mangel på hukommelse, da hukommelsen er begrænset.Ingen mangel på hukommelse, men kan lide af fragmentering af hukommelsen.

Ofte stillede spørgsmål

Q # 1) Er stack hurtigere end Heap?

Svar: En stak er hurtigere end bunke, da adgang er lineær i stak sammenlignet med bunken.

Q # 2) Hvad bruges en bunke til?

Svar: Heap bruges for det meste i algoritmer, der finder den mindste eller korteste sti mellem to punkter som Dijkstras algoritme, til at sortere ved hjælp af heap-sortering, til prioritetskøimplementeringer (min-heap) osv.

Q # 3) Hvad er en bunke? Hvad er dens typer?

Svar: En bunke er en hierarkisk, træbaseret datastruktur. En bunke er et komplet binært træ. Bunker er af to typer, dvs. Max bunke, hvor rodknudepunktet er den største blandt alle knudepunkter; Min heap, hvor rodknudepunktet er det mindste eller minimum blandt alle nøglerne.

Spørgsmål nr. 4) Hvad er fordelene ved Heap i forhold til en stak?

Svar: Den største fordel ved bunken i forhold til stakken er i bunken, hukommelsen tildeles dynamisk, og der er derfor ingen grænse for, hvor meget hukommelse der kan bruges. For det andet kan kun lokale variabler tildeles på stakken, mens vi også kan allokere globale variabler på bunken.

Q # 5) Kan Heap have dubletter?

Svar: Ja, der er ingen begrænsninger for at have noder med duplikatnøgler i bunken, da bunken er et komplet binært træ, og det opfylder ikke egenskaberne for det binære søgetræ.

Konklusion

I denne vejledning har vi diskuteret typer af dynger og dynger ved hjælp af typer af dynger. Vi har også set den detaljerede implementering af dens typer i Java.

=> Tjek den perfekte Java-træningsvejledning her.

Anbefalet læsning

^