what is heap data structure java
Tento tutoriál vysvetľuje, čo je dátová štruktúra Java Heap a súvisiace koncepty ako Min Heap, Max Heap, Heap Sort, Stack vs Heap, s príkladmi:
Hromada je špeciálna dátová štruktúra v prostredí Java. Hromada je dátová štruktúra založená na strome a možno ju klasifikovať ako úplný binárny strom. Všetky uzly haldy sú usporiadané v konkrétnom poradí.
=> Navštívte tu a pozrite si sériu školení Java pre všetkých
Čo sa dozviete:
- Halda dátová štruktúra v Jave
- Hromadiť Vs hromadu v Jave
- Záver
Halda dátová štruktúra v Jave
V dátovej štruktúre haldy je koreňový uzol porovnaný s jeho potomkami a usporiadaný podľa poradia. Takže ak a je koreňový uzol ab je jeho dieťa, potom vlastnosť, klávesa (a)> = klávesa (b) vygeneruje maximálnu hromadu.
Vyššie uvedený vzťah medzi koreňom a podradeným uzlom sa nazýva „Heap Property“.
V závislosti od poradia nadradených-uzlových uzlov je halda obvykle dvoch typov:
# 1) Max. Halda :V Max-Heap je kľúč koreňového uzla najväčší zo všetkých kľúčov v halde. Malo by sa zabezpečiť, aby rovnaká vlastnosť platila pre všetky podstromy v halde rekurzívne.
Nasledujúci diagram zobrazuje ukážku maximálnej haldy. Všimnite si, že koreňový uzol je väčší ako jeho deti.
# 2) Min. Halda :V prípade Min-Heap je kľúč koreňového uzla najmenší alebo minimálny spomedzi všetkých ostatných kľúčov prítomných v halde. Rovnako ako v halde Max, táto vlastnosť by mala byť rekurzívne pravdivá vo všetkých ostatných podstromoch v halde.
Príklad, stromu s hromadou min. je zobrazený nižšie. Ako vidíme, koreňový kľúč je najmenší zo všetkých ostatných kľúčov v halde.
Hromadnú dátovú štruktúru je možné použiť v nasledujúcich oblastiach:
- Hromady sa väčšinou používajú na implementáciu prioritných front.
- Najmä min. Halda sa dá použiť na určenie najkratších ciest medzi vrcholmi v grafe.
Ako už bolo spomenuté, dátová štruktúra haldy je kompletný binárny strom, ktorý spĺňa vlastnosť haldy pre root a deti. Táto halda sa tiež nazýva ako binárna halda .
Binárna halda
Binárna hromada spĺňa nasledujúce vlastnosti:
- Binárna hromada je úplný binárny strom. V úplnom binárnom strome sú všetky úrovne okrem poslednej úrovne úplne vyplnené. Na poslednej úrovni sú klávesy čo najviac vľavo.
- Vyhovuje to halde. Binárna halda môže byť maximálna alebo minimálna halda v závislosti od vlastnosti haldy, ktorú spĺňa.
Binárna hromada sa zvyčajne predstavuje ako pole. Pretože je to kompletný binárny strom, dá sa ľahko predstaviť ako pole. V maticovej reprezentácii binárnej haldy bude teda koreňovým prvkom A (0), kde A je pole použité na reprezentáciu binárnej haldy.
Takže všeobecne pre akékoľvek ithuzol v reprezentácii binárneho poľa haldy, A (i), môžeme reprezentovať indexy ďalších uzlov, ako je uvedené nižšie.
A ((i-1) / 2) | Predstavuje nadradený uzol |
---|---|
Prístup je rýchlejší. | Pomalšie ako stoh. |
A ((2 * i) +1) | Predstavuje ľavý podradený uzol |
A ((2 * i) +2) | Predstavuje správny podradený uzol |
Zvážte nasledujúcu binárnu haldu:
Reprezentácia poľa vyššie uvedenej binárnej haldy je nasledovná:
Ako je uvedené vyššie, halda je prekonaná podľa úroveň objednávky tj. prvkami sa na každej úrovni prechádza zľava doprava. Keď sú prvky na jednej úrovni vyčerpané, prechádzame na ďalšiu úroveň.
Ďalej implementujeme binárnu haldu v Jave.
Nasledujúci program demonštruje binárnu haldu v prostredí 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 Výkon:
nHeap = 7 4 6 1 3 2 5
Min. Halda v Jave
Hromada min v jazyku Java je kompletný binárny strom. V min halde je koreňový uzol menší ako všetky ostatné uzly v halde. Všeobecne je hodnota kľúča každého interného uzla menšia alebo rovnaká ako jeho podradené uzly.
Pokiaľ ide o reprezentáciu poľa haldy, ak je uzol uložený v polohe „i“, potom je jeho ľavý podradený uzol uložený v polohe 2i + 1 a pravý podriadený uzol je v polohe 2i + 2. Pozícia (i-1) / 2 vráti svoj nadradený uzol.
Nižšie sú uvedené rôzne operácie podporované technológiou min-heap.
# 1) Vložiť (): Spočiatku je nový kľúč pridaný na koniec stromu. Ak je kľúč väčší ako jeho nadradený uzol, potom sa vlastnosť haldy zachová. V opačnom prípade musíme klávesu prejsť hore, aby sme splnili vlastnosť haldy. Operácia vloženia do minimálnej haldy trvá O (log n).
# 2) extractMin (): Táto operácia odstráni minimálny prvok z haldy. Upozorňujeme, že vlastnosť haldy by sa mala zachovať po odstránení koreňového prvku (minimálneho prvku) z haldy. Celá táto operácia trvá O (Logn).
# 3) getMin (): getMin () vráti koreň haldy, ktorá je tiež minimálnym prvkom. Táto operácia sa vykoná v čase O (1).
Ďalej je uvedený príklad stromu pre haldu Min.

Vyššie uvedený diagram zobrazuje strom haldy min. Vidíme, že koreň stromu je minimálny prvok v strome. Pretože je koreň na pozícii 0, jeho ľavé dieťa je umiestnené na 2 * 0 + 1 = 1 a pravé dieťa je na 2 * 0 + 2 = 2.
Algoritmus minimálnej haldy
Nižšie je uvedený algoritmus na vytvorenie minimálnej haldy.
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); } }
Minimálna implementácia haldy v jazyku Java
Min haldu môžeme implementovať buď pomocou radov polí alebo prioritných frontov. Implementácia minimálnej haldy pomocou prioritných frontov je predvolenou implementáciou, pretože prioritná fronta sa implementuje ako minimálna halda.
Nasledujúci program Java implementuje min haldu pomocou polí. Tu použijeme reprezentáciu poľa pre haldu a potom použijeme funkciu heapify na udržanie vlastnosti haldy každého prvku pridaného do haldy. Nakoniec zobrazíme haldu.
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()); } }
Výkon:

Max. Hromada v Jave
Maximálna hromada je tiež kompletný binárny strom. V maximálnej halde je koreňový uzol väčší alebo rovnaký ako podradené uzly. Všeobecne je hodnota ktoréhokoľvek interného uzla v maximálnej halde väčšia alebo rovnaká ako jeho podradené uzly.
Zatiaľ čo maximálna halda je namapovaná na pole, ak je akýkoľvek uzol uložený na pozícii „i“, potom jeho ľavé dieťa je uložené na 2i +1 a pravé dieťa je uložené na 2i + 2.
Typická maximálna hromada bude vyzerať takto:

Na vyššie uvedenom diagrame vidíme, že koreňový uzol je najväčší v halde a jeho podradené uzly majú hodnoty menšie ako koreňový uzol.
Podobne ako min-halda, aj maximálna halda môže byť reprezentovaná ako pole.
Takže ak A je pole, ktoré predstavuje Max. Hromadu, potom A (0) je koreňový uzol. Podobne, ak A (i) je akýkoľvek uzol v maximálnej halde, potom sú nasledujúce susedné uzly, ktoré je možné reprezentovať pomocou poľa.
- A ((i-1) / 2) predstavuje nadradený uzol A (i).
- A ((2i +1)) predstavuje ľavý podradený uzol A (i).
- A (2i + 2) vráti pravý podradený uzol A (i).
Ďalej sú uvedené operácie, ktoré je možné vykonať na Max. Halde.
# 1) Vložiť: Operácia vloženia vloží novú hodnotu do maximálneho haldy. Vkladá sa na koniec stromu. Ak je nový kľúč (hodnota) menší ako jeho nadradený uzol, potom sa vlastnosť haldy zachová. V opačnom prípade musí byť strom heapifikovaný, aby sa zachovala vlastnosť haldy.
bezplatný softvér sql pre Windows 10
Časová zložitosť operácie vloženia je O (log n).
# 2) ExtractMax: Operácia ExtractMax odstráni maximálny prvok (root) z maximálnej haldy. Operácia tiež heapifikuje maximálnu haldu na udržanie vlastnosti haldy. Časová zložitosť tejto operácie je O (log n).
# 3) getMax: Operácia getMax vráti koreňový uzol maximálnej haldy s časovou zložitosťou O (1).
Nižšie uvedený program Java implementuje maximálnu hromadu. Tu používame ArrayList, aby sme reprezentovali prvky maximálnej haldy.
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); } }
Výkon:

Minimálna halda prioritného frontu v Jave
Dátovú štruktúru prioritného frontu v Jave je možné priamo použiť na predstavenie minimálnej haldy. Predvolene implicitný front implementuje minimálnu haldu.
Nasledujúci program demonštruje min haldy v Jave pomocou fronty priorít.
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() + ' '); } }
Výkon:

Maximálna halda prioritného frontu v Jave
Aby sme reprezentovali maximálnu hromadu v Jave pomocou frontu priorít, musíme na zvrátenie minimálnej haldy použiť Collections.reverseOrder. Fronta priorít predstavuje v Java priamo haldu.
V nasledujúcom programe sme implementovali Max. Haldu pomocou fronty priorít.
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() + ' '); } }
Výkon:

Hromadné triedenie v Jave
Heap sort je porovnávacia triediaca technika podobná selekcii výberov, pri ktorej vyberáme maximálny prvok v poli pre každú iteráciu. Heap sort využíva dátovú štruktúru haldy a triedi prvky vytvorením minimálnej alebo maximálnej haldy z prvkov poľa, ktoré sa majú triediť.
Už sme diskutovali o tom, že v min a max halde obsahuje koreňový uzol minimálny a maximálny prvok poľa. Pri triedení haldy sa koreňový prvok haldy (min. Alebo max.) Odstráni a presunie sa do zoradeného poľa. Zvyšná halda sa potom heapifikuje, aby sa zachovala vlastnosť haldy.
Musíme teda vykonať dva kroky rekurzívne, aby sme dané pole zoradili pomocou haldy.
- Vytvorte z daného poľa hromadu.
- Opakovane vyberte koreňový prvok z haldy a presuňte ho do zoradeného poľa. Heapify zvyšnú hromadu.
Časová zložitosť triedenia haldy je vo všetkých prípadoch O (n log n). Zložitosť priestoru je O (1).
Algoritmus haldy triedenia v Jave
Ďalej sú uvedené algoritmy triedenia haldy na zoradenie daného poľa vo vzostupnom a zostupnom poradí.
# 1) Algoritmus triedenia hromád na zoradenie vzostupne:
- Vytvorte maximálnu hromadu pre dané pole, ktoré sa má zoradiť.
- Odstráňte koreň (maximálna hodnota vo vstupnom poli) a presuňte ho do zoradeného poľa. Posledný prvok v poli umiestnite ku koreňu.
- Heapify nový koreň haldy.
- Opakujte kroky 1 a 2, kým nebude zoradené celé pole.
# 2) Algoritmus triedenia hromád na zoradenie v zostupnom poradí:
- Zostavte minimálnu haldu pre dané pole.
- Odstráňte koreň (minimálna hodnota v poli) a vymeňte ho za posledný prvok v poli.
- Heapify nový koreň haldy.
- Opakujte kroky 1 a 2, kým nebude zoradené celé pole.
Implementácia haldy triedenia v Jave
Nižšie uvedený program Java používa triedenie hald na zoradenie poľa vo vzostupnom poradí. Z tohto dôvodu najskôr zostrojíme maximálnu haldu a potom rekurzívne zameníme a heapifikujeme koreňový prvok, ako je uvedené vo vyššie uvedenom 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)); } }
Výkon:

Celková časová zložitosť techniky triedenia haldy je O (nlogn). Časová zložitosť techniky heapify je O (logn). Zatiaľ čo časová náročnosť budovania haldy je O (n).
Hromadiť Vs hromadu v Jave
Uveďme teraz tabuľku niektorých rozdielov medzi dátovou štruktúrou Stack a hromadou.
Stoh Halda Zásobník je lineárna dátová štruktúra. Hromada je hierarchická dátová štruktúra. Nasleduje objednávanie LIFO (Last In, First Out). Traverz je v rovnom poradí. Používa sa hlavne na pridelenie statickej pamäte. Používa sa na dynamické prideľovanie pamäte. Pamäť je pridelená súvisle. Pamäť je alokovaná na náhodných miestach. Veľkosť stohu je podľa operačného systému obmedzená. Operačný systém nepresadzuje žiadne obmedzenie veľkosti haldy. Zásobník má prístup iba k miestnym premenným. Halda má pridelené globálne premenné. Alokácia / deallocation pamäte je automatická. Alokácia / deallocation musí byť vykonaná manuálne programátorom. Zásobník je možné implementovať pomocou polí, prepojených zoznamov, zoznamov polí atď. Alebo iných lineárnych dátových štruktúr. Halda je implementovaná pomocou polí alebo stromov. Náklady na údržbu, ak sú nižšie. Náročnejšie na údržbu. Môže to mať za následok nedostatok pamäte, pretože je obmedzená. Nedostatok pamäte, ale môže trpieť fragmentáciou pamäte.
často kladené otázky
Otázka 1) Je stack rýchlejší ako Heap?
Odpoveď: Zásobník je rýchlejší ako halda, pretože prístup je v zásobníku lineárny v porovnaní s hromadou.
Otázka 2) Na čo sa hromada používa?
Odpoveď: Halda sa väčšinou používa v algoritmoch, ktoré nájdu minimálnu alebo najkratšiu cestu medzi dvoma bodmi, ako je Dijkstrov algoritmus, na triedenie pomocou haldy, na implementáciu prioritných front (min. Halda) atď.
Otázka 3) Čo je to halda? Aké sú jeho typy?
Odpoveď: Hromada je hierarchická stromová dátová štruktúra. Hromada je úplný binárny strom. Haldy sú dvoch typov, t. J. Maximálna halda, v ktorej je koreňový uzol najväčší zo všetkých uzlov; Min. Halda, v ktorej je koreňový uzol najmenší alebo minimálny spomedzi všetkých kľúčov.
Otázka č. 4) Aké sú výhody haldy oproti stohu?
Odpoveď: Hlavná výhoda haldy nad zásobníkom je v halde, pamäť je dynamicky alokovaná, a preto neexistuje nijaké obmedzenie, koľko pamäte je možné použiť. Po druhé, na zásobník sa dajú alokovať iba lokálne premenné, zatiaľ čo na hromadu môžeme prideliť aj globálne premenné.
Otázka č. 5) Môže mať halda duplikáty?
Odpoveď: Áno, neexistujú žiadne obmedzenia, pokiaľ ide o to, aby uzly s duplikátnymi kľúčmi boli v halde, pretože halda je úplný binárny strom a nespĺňa vlastnosti binárneho vyhľadávacieho stromu.
Záver
V tomto tutoriáli sme diskutovali o typoch haldy a triedení haldy pomocou typov haldy. Videli sme tiež podrobnú implementáciu jeho typov v Jave.
=> Vyskúšajte Sprievodcu dokonalým školením Java tu.
Odporúčané čítanie
- Výukový program pre graf Java - Ako implementovať dátovú štruktúru grafu
- Úvod do dátových štruktúr v C ++
- Hromadné triedenie v C ++ s príkladmi
- Dátová štruktúra stromu a haldy AVL v C ++
- Štruktúra dát binárneho stromu v C ++
- Dátová štruktúra frontu v C ++ s ilustráciou
- Dátová štruktúra kruhového prepojeného zoznamu v C ++ s ilustráciou
- Základy jazyka Java: Java Syntax, trieda Java a základné koncepty Java