what is heap data structure java
Denna handledning förklarar vad som är Java Heap-datastruktur och relaterade begrepp som Min Heap, Max Heap, Heap Sort, Stack vs Heap med exempel:
En hög är en speciell datastruktur i Java. En hög är en trädbaserad datastruktur och kan klassificeras som ett komplett binärt träd. Alla noder i högen är ordnade i en specifik ordning.
=> Besök här för att se Java Training Series för alla
Vad du kommer att lära dig:
Heap Datastruktur i Java
I heapdatastrukturen jämförs rotnoden med sina underordnade och ordnas enligt ordningen. Så om a är en rotnod och b är dess underordnade, så är egenskapen, nyckel (a)> = nyckel (b) genererar en maxhöjd.
Ovanstående förhållande mellan roten och den underordnade noden kallas ”Heap Property”.
Beroende på ordningen på föräldra-barnnoder är högen i allmänhet av två typer:
# 1) Max-Heap :I en Max-Heap är rotnodnyckeln den största av alla nycklar i högen. Det bör säkerställas att samma egenskap är sant för alla subtrees i högen rekursivt.
Nedanstående diagram visar ett exempel på Max Heap. Observera att rotnoden är större än dess underordnade.
# 2) Min-Heap :När det gäller en Min-Heap är rotnodnyckeln den minsta eller minsta bland alla andra nycklar som finns i högen. Som i Max heap bör den här egenskapen vara rekursivt sant i alla andra subtrees i högen.
Ett exempel, av ett minhögt träd, visas nedan. Som vi kan se är rotnyckeln den minsta av alla andra nycklar i högen.
En heap-datastruktur kan användas i följande områden:
- Heaps används mest för att implementera prioritetsköer.
- Speciellt min-heap kan användas för att bestämma de kortaste banorna mellan topparna i en graf.
Som redan nämnts är heapdatastrukturen ett komplett binärt träd som uppfyller heapegenskapen för root och barnen. Denna hög kallas också som en binär hög .
Binär hög
En binär hög uppfyller egenskaperna nedan:
- En binär hög är ett komplett binärt träd. I ett komplett binärt träd fylls alla nivåer utom den sista nivån helt. På den sista nivån är tangenterna så långt som möjligt till vänster.
- Det tillfredsställer högegenskapen. Den binära heapen kan vara max eller min-heap beroende på den heap-egenskap den uppfyller.
En binär hög representeras normalt som en matris. Eftersom det är ett komplett binärt träd kan det enkelt representeras som en matris. I en matrisrepresentation av binär hög kommer således rotelementet att vara A (0) där A är den matris som används för att representera den binära högen.
Så i allmänhet för alla jagthnoden i den binära heap-arrayrepresentationen, A (i), kan vi representera index för andra noder som visas nedan.
| A ((i-1) / 2) | Representerar föräldernoden |
|---|---|
| Åtkomst är snabbare. | Långsammare än stacken. |
| A ((2 * i) +1) | Representerar den vänstra barnnoden |
| A ((2 * i) +2) | Representerar rätt barn nod |
Tänk på följande binära hög:
Arrayrepresentationen för den minsta binära högen ovan är som följer:
Som visas ovan passeras högen enligt nivåordning det vill säga elementen korsas från vänster till höger på varje nivå. När elementen på en nivå är uttömda går vi vidare till nästa nivå.
Därefter implementerar vi den binära högen i Java.
Nedanstående program visar den binära högen 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 hög i Java
En min-hög i Java är ett komplett binärt träd. I min-heap är rotnoden mindre än alla andra noder i heapen. I allmänhet är nyckelvärdet för varje intern nod mindre än eller lika med dess undernoder.
När det gäller arrayrepresentation av min-heap, om en nod lagras i position 'i', lagras dess vänstra barn-nod i position 2i + 1 och då är den högra barn-noden i position 2i + 2. Positionen (i-1) / 2 returnerar sin överordnade nod.
Nedan listas de olika operationerna som stöds av min-heap.
# 1) Infoga (): Ursprungligen läggs en ny nyckel till i slutet av trädet. Om nyckeln är större än dess överordnade nod, behålls heap-egenskapen. Annars måste vi korsa nyckeln uppåt för att uppfylla heapegenskapen. Insättning i min hög tar O (log n) tid.
# 2) extractMin (): Denna åtgärd tar bort minimielementet från högen. Observera att egenskapen heap ska bibehållas efter att rotelementet (min-elementet) har tagits bort från heapen. Hela denna operation tar O (Logn).
# 3) getMin (): getMin () returnerar roten till högen som också är minimielementet. Denna operation utförs i O (1) tid.
Nedan följer ett exempel på ett träd för en Min-hög.
Ovanstående diagram visar ett minhögt träd. Vi ser att trädets rot är det minsta elementet i trädet. Eftersom roten är på plats 0 placeras dess vänstra barn på 2 * 0 + 1 = 1 och höger barn är på 2 * 0 + 2 = 2.
Min högalgoritm
Nedan följer algoritmen för att bygga en min-hög.
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 höjdimplementering i Java
Vi kan implementera min-högen antingen med hjälp av array- eller prioritetsköer. Implementering av minhög med prioritetsköer är standardimplementeringen eftersom en prioritetskö implementeras som minhög.
Följande Java-program implementerar min-högen med hjälp av Arrays. Här använder vi arrayrepresentation för heap och använder sedan heapify-funktionen för att bibehålla heap-egenskapen för varje element som läggs till i heapen. Slutligen visar vi högen.
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:
Max Heap I Java
En maxhög är också ett komplett binärt träd. I en maxhög är rotnoden större än eller lika med undernoderna. I allmänhet är värdet på en intern nod i en maxhöjd större än eller lika med dess undernoder.
Medan maxheap mappas till en matris, om någon nod lagras i position 'i', lagras dess vänstra barn vid 2i +1 och det högra barnet lagras vid 2i + 2.
Typisk Max-heap ser ut som visas nedan:
I ovanstående diagram ser vi att rotnoden är den största i högen och dess undernoder har värden mindre än rotnoden.
På samma sätt som min-heap kan max heap också representeras som en matris.
Så om A är en matris som representerar Max heap så är A (0) rotnoden. På samma sätt, om A (i) är någon nod i maxheapen, är följande andra intilliggande noder som kan representeras med hjälp av en matris.
- A ((i-1) / 2) representerar modernoden för A (i).
- A ((2i +1)) representerar den vänstra barnnoden för A (i).
- A (2i + 2) returnerar högerbarnod för A (i).
De åtgärder som kan utföras på Max Heap ges nedan.
# 1) Infoga: Infoga operation infogar ett nytt värde i max heap-trädet. Den sätts in i slutet av trädet. Om den nya nyckeln (värdet) är mindre än dess överordnade nod, behålls heap-egenskapen. Annars måste trädet heapifieras för att bibehålla heapegenskapen.
testplanprov för webbapplikation
Tidskomplexiteten för insatsoperationen är O (log n).
# 2) ExtractMax: Operationen ExtractMax tar bort det maximala elementet (root) från maxheapen. Operationen heapifierar också maxhögen för att underhålla heapegenskapen. Tids komplexiteten för denna operation är O (log n).
# 3) getMax: getMax-operationen returnerar rotnoden för maxheapen med tidskomplexiteten för O (1).
Nedanstående Java-program implementerar maxhögen. Vi använder ArrayList här för att representera maxheapelementen.
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:
Prioritetskö Min hög i Java
Prioritetskodatastrukturen i Java kan användas direkt för att representera min-högen. Som standard implementerar prioritetskön min-heap.
Nedanstående program visar min-högen i Java med hjälp 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() + ' '); } } Produktion:
Prioritetskö Max Heap i Java
För att representera maxhögen i Java med hjälp av prioritetskön måste vi använda Collections.reverseOrder för att vända minhögen. Prioritetskön representerar direkt en minhög i Java.
Vi har implementerat Max Heap med en prioritetskö i nedanstå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:
Högsortering i Java
Heapsortering är en jämförelsesorteringsteknik som liknar urvalsortering där vi väljer ett maximalt element i matrisen för varje iteration. Heap sort använder sig av Heap datastruktur och sorterar elementen genom att skapa min eller max heap ur arrayelementen som ska sorteras.
Vi har redan diskuterat att rotnoden innehåller min- och maxelement i arrayen i min- och maxheap. I högsortering tas rotelementet på högen (min eller max) bort och flyttas till den sorterade matrisen. Den återstående högen höjdas sedan för att upprätthålla högen.
Så vi måste utföra två steg rekursivt för att sortera den givna matrisen med hjälp av högsortering.
- Bygg en hög från den givna matrisen.
- Ta upp rotelementet upprepade gånger från högen och flytta det till den sorterade matrisen. Heapify den återstående högen.
Tidskomplexitet för högsortering är O (n log n) i alla fall. Utrymmets komplexitet är O (1).
Högsorteringsalgoritm i Java
Nedan visas algoritmerna för högsortering för att sortera den givna matrisen i stigande och fallande ordning.
# 1) Heapsorteringsalgoritm för att sortera i stigande ordning:
- Skapa en maxhög för den givna matrisen som ska sorteras.
- Ta bort roten (maximalt värde i inmatningsmatrisen) och flytta den till den sorterade matrisen. Placera det sista elementet i arrayen vid roten.
- Heapify den nya roten till högen.
- Upprepa steg 1 och 2 tills hela matrisen är sorterad.
# 2) Heapsorteringsalgoritm för att sortera i fallande ordning:
- Konstruera en min hög för den givna matrisen.
- Ta bort roten (minimivärde i matrisen) och byt den med det sista elementet i matrisen.
- Heapify den nya roten till högen.
- Upprepa steg 1 och 2 tills hela matrisen är sorterad.
Implementering av högsortering i Java
Nedanstående Java-program använder högsortering för att sortera en matris i stigande ordning. För detta konstruerar vi först en maxheap och byter sedan rekursivt och heapify rotelementet som anges i algoritmen ovan.
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:
Den övergripande tidskomplexiteten för högsorteringstekniken är O (nlogn). Tidskomplexiteten hos heapify-tekniken är O (logn). Medan tidskomplexiteten för att bygga högen är O (n).
Stack mot högen i Java
Låt oss nu tabellisera några av skillnaderna mellan en stack-datastruktur och heap.
Stack Högen En stack är en linjär datastruktur. En hög är en hierarkisk datastruktur. Följer beställning av LIFO (Last In, First Out). Traversal är i jämn ordning. Används mest för statisk minnestilldelning. Används för dynamisk minnestilldelning. Minne tilldelas sammanhängande. Minne allokeras på slumpmässiga platser. Stackstorleken är begränsad enligt operativsystemet. Ingen begränsning av högstorleken som styrs av operativsystemet. Stack har endast tillgång till lokala variabler. Heap har globala variabler tilldelade. Tilldelningen / fördelningen av minnet sker automatiskt. Tilldelning / deallocation måste göras manuellt av programmeraren. Stapeln kan implementeras med hjälp av Arrays, Linked List, ArrayList, etc. eller andra linjära datastrukturer. Heap implementeras med hjälp av arrays eller träd. Kostnad för underhåll om mindre. Dyrare att underhålla. Kan leda till minnesbrist eftersom minnet är begränsat. Ingen brist på minne men kan drabbas av minnesfragmentering.
Vanliga frågor
F # 1) Är stacken snabbare än Heap?
Svar: En stack är snabbare än hög eftersom åtkomst är linjär i stapel jämfört med högen.
F # 2) Vad används en hög till?
Svar: Heap används mestadels i algoritmer som hittar den minsta eller kortaste vägen mellan två punkter som Dijkstras algoritm, för att sortera med hopsortering, för prioritetsköimplementeringar (min-heap) etc.
F # 3) Vad är en hög? Vilka är dess typer?
Svar: En hög är en hierarkisk, trädbaserad datastruktur. En hög är ett komplett binärt träd. Heaps är av två typer dvs Max heap där rotnoden är den största bland alla noder; Min höjd där rotnoden är den minsta eller minsta bland alla tangenter.
F # 4) Vilka är fördelarna med Heap jämfört med en stack?
Svar: Den största fördelen med högen jämfört med stacken är i högen, minnet allokeras dynamiskt och det finns därför ingen gräns för hur mycket minne som kan användas. För det andra kan endast lokala variabler tilldelas på stacken medan vi också kan fördela globala variabler på högen.
F # 5) Kan Heap ha dubbletter?
Svar: Ja, det finns inga begränsningar för att ha noder med dubbla nycklar i högen eftersom högen är ett komplett binärt träd och det inte uppfyller egenskaperna för det binära sökträdet.
Slutsats
I denna handledning har vi diskuterat typerna av hög och hög med hjälp av typer av hög. Vi har också sett den detaljerade implementeringen av dess typer i Java.
=> Kolla in den perfekta Java-träningsguiden här.
Rekommenderad läsning
- Java-grafhandledning - Hur man implementerar diagramdatastruktur
- Introduktion till datastrukturer i C ++
- Heapsortering i C ++ med exempel
- AVL-träd- och högdatastruktur i C ++
- Datastruktur för binärt träd i C ++
- Kodatastruktur i C ++ med illustration
- Cirkulär länkad datastruktur i C ++ med illustration
- Java Basics: Java Syntax, Java Class och Core Java Concepts
