what is heap data structure java
Ovaj vodič objašnjava što je struktura podataka Java Heap podataka i srodni koncepti kao što su Min Heap, Max Heap, Heap Sort, Stack vs Heap s primjerima:
Hrpa je posebna struktura podataka u Javi. Hrpa je struktura podataka koja se temelji na stablu i može se klasificirati kao cjelovito binarno stablo. Svi čvorovi hrpe poredani su određenim redoslijedom.
=> Posjetite ovdje da biste vidjeli seriju Java treninga za sve
Što ćete naučiti:
Struktura podataka gomile u Javi
U strukturi podataka hrpe korijenski čvor uspoređuje se sa svojom podređenom jedinicom i slaže prema redoslijedu. Dakle, ako je a korijenski čvor, a b njegovo dijete, tada je svojstvo, tipka (a)> = tipka (b) generirat će maksimalnu hrpu.
Gornji odnos između korijena i podređenog čvora naziva se 'Svojstvo hrpe'.
Ovisno o redoslijedu nadređenih čvorova, gomila je obično dvije vrste:
# 1) Max-Heap :U Max-Heap-u ključ korijenskog čvora je najveći od svih ključeva u hrpi. Treba osigurati da isto svojstvo vrijedi za sva podstabla u hrpi rekurzivno.
Dijagram dolje prikazuje Primjer maksimalne hrpe. Primijetite da je korijenski čvor veći od njegove djece.
# 2) Min-hrpa :U slučaju Min-Heap, ključ korijenskog čvora najmanji je ili najmanji među svim ostalim ključevima prisutnima u hrpi. Kao i u Max hrpi, ovo bi svojstvo trebalo biti rekurzivno točno u svim ostalim podstablima u hrpi.
Primjer, stabla Min-heap, prikazano je dolje. Kao što vidimo, korijenski ključ najmanji je od svih ostalih ključeva u hrpi.
Struktura podataka hrpe može se koristiti u sljedećim područjima:
- Gomile se uglavnom koriste za implementaciju prioritetnih redova.
- Posebno se min-hrpa može koristiti za određivanje najkraćih putova između vrhova u Grafu.
Kao što je već spomenuto, struktura podataka hrpe cjelovito je binarno stablo koje zadovoljava svojstvo hrpe za root i djecu. Ova se hrpa također naziva i binarna hrpa .
Binarna hrpa
Binarna hrpa ispunjava sljedeća svojstva:
- Binarna hrpa je kompletno binarno stablo. U cjelovitom binarnom stablu sve razine, osim posljednje, potpuno su ispunjene. Na posljednjoj razini tipke su što je više moguće lijevo.
- Zadovoljava svojstvo hrpe. Binarna hrpa može biti max ili min-heap, ovisno o svojstvu hrpe koje zadovoljava.
Binarna hrpa obično je predstavljena kao niz. Kako se radi o cjelovitom binarnom stablu, lako se može predstaviti kao niz. Tako će u prikazu niza binarne hrpe korijenski element biti A (0) gdje je A niz koji se koristi za predstavljanje binarne hrpe.
Dakle, općenito za bilo koji ithčvor u binarnom prikazu hrpe niza, A (i), možemo predstaviti indekse ostalih čvorova kako je prikazano dolje.
| A ((i-1) / 2) | Predstavlja nadređeni čvor |
|---|---|
| Pristup je brži. | Sporiji od hrpe. |
| A ((2 * i) +1) | Predstavlja lijevi podređeni čvor |
| A ((2 * i) +2) | Predstavlja pravi podređeni čvor |
Razmotrite sljedeću binarnu hrpu:
Prikaz niza gornje min binarne hrpe je kako slijedi:
Kao što je gore prikazano, hrpa se prelazi prema poredak na razini tj. Elementi se prelaze slijeva udesno na svakoj razini. Kada su elementi na jednoj razini iscrpljeni, prelazimo na sljedeću razinu.
Dalje, implementirat ćemo binarnu hrpu u Javu.
Program u nastavku prikazuje binarnu hrpu u Javi.
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 Izlaz:
nHeap = 7 4 6 1 3 2 5
Min hrpa u Javi
Min-hrpa u Javi potpuno je binarno stablo. U min-hrpi, korijenski čvor je manji od svih ostalih čvorova u hrpi. Općenito, ključna vrijednost svakog unutarnjeg čvora manja je ili jednaka njegovim podređenim čvorovima.
Što se tiče prikaza niza min-hrpe, ako je čvor pohranjen na poziciji 'i', tada je njegov lijevi podređeni čvor pohranjen na položaju 2i + 1, a zatim je desni podređeni čvor na položaju 2i + 2. Položaj (i-1) / 2 vraća svoj nadređeni čvor.
U nastavku su navedene razne operacije podržane min-heapom.
# 1) Umetni (): U početku se na kraju stabla dodaje novi ključ. Ako je ključ veći od nadređenog čvora, svojstvo hrpe se održava. U suprotnom, trebamo prijeći ključ prema gore kako bismo ispunili svojstvo hrpe. Operacija umetanja u minimalnu hrpu traje O (log n) vrijeme.
# 2) extractMin (): Ovom operacijom uklanja se minimalni element iz hrpe. Imajte na umu da bi svojstvo hrpe trebalo održavati nakon uklanjanja korijenskog elementa (min elementa) iz hrpe. Cijela ova operacija traje O (Logn).
# 3) getMin (): getMin () vraća korijen hrpe koji je ujedno i minimalni element. Ova se operacija vrši u O (1) vremenu.
Dano u nastavku je primjer stabla za Min-hrpu.
Gornji dijagram prikazuje stablo min-hrpe. Vidimo da je korijen stabla minimalni element u stablu. Kako se korijen nalazi na mjestu 0, njegovo je lijevo dijete postavljeno na 2 * 0 + 1 = 1, a desno dijete na 2 * 0 + 2 = 2.
Minimalni algoritam hrpe
Dolje je dan algoritam za izgradnju min-hrpe.
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); } }Implementacija minimalne hrpe u Javi
Min-hrpu možemo implementirati bilo pomoću niza ili redova prioriteta. Implementacija min-hrpe pomoću prioritetnih redova zadana je implementacija jer se prioritetni red implementira kao min-heap.
Sljedeći Java program implementira min-hrpu pomoću nizova. Ovdje koristimo prikaz niza za hrpu, a zatim primjenjujemo funkciju heapify za održavanje svojstva hrpe svakog elementa dodanog u hrpu. Napokon prikazujemo hrpu.
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()); } } Izlaz:
Maksimalna hrpa u Javi
Maksimalna hrpa također je potpuno binarno stablo. U maksimalnoj hrpi, korijenski čvor veći je ili jednak podređenim čvorovima. Općenito, vrijednost bilo kojeg unutarnjeg čvora u maksimalnoj hrpi veća je ili jednaka njegovim podređenim čvorovima.
Dok se maksimalna gomila preslikava na niz, ako je bilo koji čvor pohranjen na položaju 'i', tada se njegovo lijevo podređeno mjesto pohranjuje na 2i +1, a desno podređeno na 2i + 2.
Tipični Max-heap izgledat će kako je prikazano u nastavku:
U gornjem dijagramu vidimo da je korijenski čvor najveći u hrpi i da njegovi podređeni čvorovi imaju vrijednosti manje od korijenskog čvora.
Slično min-heap-u, max hrpa također se može predstaviti kao niz.
Dakle, ako je A niz koji predstavlja Max hrpu, tada je A (0) korijenski čvor. Slično tome, ako je A (i) bilo koji čvor u maksimalnoj hrpi, tada su sljedeći ostali susjedni čvorovi koji se mogu predstaviti pomoću niza.
- A ((i-1) / 2) predstavlja nadređeni čvor A (i).
- A ((2i +1)) predstavlja lijevi podređeni čvor A (i).
- A (2i + 2) vraća desni podređeni čvor A (i).
Operacije koje se mogu izvoditi na Max Heap-u dane su u nastavku.
# 1) Umetni: Operacija umetanja ubacuje novu vrijednost u stablo maksimalne hrpe. Umeće se na kraj stabla. Ako je novi ključ (vrijednost) manji od nadređenog čvora, tada se zadržava svojstvo hrpe. Inače, stablo treba gomilati kako bi se održalo svojstvo gomile.
tehnike izazivanja zahtjeva u softverskom inženjerstvu
Složenost vremena rada umetka je O (log n).
# 2) ExtractMax: Operacija ExtractMax uklanja maksimalni element (korijen) iz maksimalne hrpe. Operacija također gomila maksimalnu gomilu radi održavanja svojstva gomile. Vremenska složenost ove operacije je O (log n).
# 3) getMax: operacija getMax vraća korijenski čvor maksimalne hrpe s vremenskom složenošću O (1).
Sljedeći Java program implementira maksimalnu hrpu. Ovdje koristimo ArrayList za predstavljanje maksimalnih elemenata hrpe.
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); } } Izlaz:
Minimalna hrpa prioriteta u Javi
Struktura podataka reda prioriteta u Javi može se izravno koristiti za predstavljanje min-hrpe. Prema zadanim postavkama, prioritetni red implementira min-hrpu.
Program u nastavku prikazuje min-hrpu u Javi pomoću reda prioriteta.
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() + ' '); } } Izlaz:
Prioritetni red Maksimalna hrpa u Javi
Da bismo predstavili maksimalnu hrpu u Javi pomoću reda prioriteta, moramo koristiti Collections.reverseOrder da preokrenemo min-hrpu. Prioritetni red izravno predstavlja min-hrpu u Javi.
Max Heap smo implementirali pomoću reda prioriteta u donjem programu.
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() + ' '); } } Izlaz:
Razvrstavanje hrpe u Javi
Heap sort je tehnika usporedbe sortiranja slična sortiranju odabira u kojoj za svaku iteraciju odabiremo maksimalni element u polju. Heap sort koristi strukturu podataka Heap i sortira elemente stvaranjem min ili max hrpe od elemenata niza koji će se sortirati.
Već smo raspravljali o tome da u hrpi min i max korijenski čvor sadrži element minimum i maksimum niza. U sortiranju hrpe, korijenski element hrpe (min ili max) uklanja se i premješta u sortirani niz. Preostala hrpa tada se gomila kako bi se održalo svojstvo hrpe.
Dakle, moramo izvršiti dva koraka rekurzivno za sortiranje datog niza pomoću heap sort.
- Izgradi hrpu iz zadanog niza.
- Više puta uklanjajte korijenski element iz hrpe i premjestite ga u razvrstani niz. Preopteretiti preostalu hrpu.
Složenost vremena sortiranja hrpe je O (n log n) u svim slučajevima. Složenost prostora je O (1).
Algoritam sortiranja hrpe u Javi
Dolje su dati algoritmi sortiranja hrpe za sortiranje datog niza u rastućem i silaznom redoslijedu.
# 1) algoritam sortiranja hrpe za sortiranje u uzlaznom redoslijedu:
- Stvorite maksimalnu hrpu za sortiranje datog polja.
- Izbrišite korijen (maksimalna vrijednost u ulaznom polju) i premjestite ga u sortirani niz. Stavite posljednji element u polje u korijen.
- Ojačajte novi korijen hrpe.
- Ponavljajte korake 1 i 2 dok se cijeli niz ne sortira.
# 2) Algoritam sortiranja hrpe za sortiranje u opadajućem redoslijedu:
- Konstruirajte min hrpu za zadati niz.
- Uklonite korijen (minimalna vrijednost u polju) i zamijenite ga posljednjim elementom u polju.
- Ojačajte novi korijen hrpe.
- Ponavljajte korake 1 i 2 dok se cijeli niz ne sortira.
Implementacija sortiranja hrpe u Javi
Ispod navedeni Java program koristi sortiranje hrpe za sortiranje niza u rastućem redoslijedu. Za to prvo konstruiramo maksimalnu hrpu, a zatim rekurzivno zamijenimo i gomilamo korijenski element kako je navedeno u gornjem algoritmu.
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)); } } Izlaz:
Ukupna vremenska složenost tehnike sortiranja hrpe je O (nlogn). Vremenska složenost tehnike Heapify je O (logn). Dok je vremenska složenost izgradnje gomile O (n).
Složite vs hrpu u Javi
Idemo sada tabularizirati neke razlike između strukture podataka Stacka i hrpe.
Stog Hrpa Stog je linearna struktura podataka. Hrpa je hijerarhijska struktura podataka. Slijedi narudžbu LIFO (zadnji ulaz, prvi izlaz). Prelazak je u ravnomjernom redoslijedu. Uglavnom se koristi za statičku dodjelu memorije. Koristi se za dinamičku dodjelu memorije. Memorija se dodjeljuje susjedno. Memorija se raspoređuje na slučajnim mjestima. Veličina hrpe ograničena je u skladu s operativnim sustavom. Nema ograničenja veličine hrpe koje nameće operativni sustav. Stog ima pristup samo lokalnim varijablama. Heap ima dodijeljene globalne varijable. Dodjela / oslobađanje memorije je automatsko. Dodjeljivanje / preusmjeravanje programer mora izvršiti ručno. Stog se može implementirati pomoću nizova, povezanog popisa, arraylist-a itd. Ili bilo koje druge linearne strukture podataka. Hrpa se implementira pomoću nizova ili stabala. Troškovi održavanja ako su manji. Skuplje za održavanje. Može rezultirati nedostatkom memorije jer je memorija ograničena. Nema manjka memorije, ali može patiti od fragmentacije memorije.
Često postavljana pitanja
P # 1) Je li stog brži od Heap-a?
Odgovor: Stog je brži od hrpe jer je pristup linearnom u hrpi u usporedbi s hrpom.
P # 2) Za što se koristi hrpa?
Odgovor: Hrpa se uglavnom koristi u algoritmima koji pronalaze najmanji ili najkraći put između dviju točaka poput Dijkstrinog algoritma, za sortiranje pomoću sortiranja hrpe, za implementacije reda prioriteta (min-heap) itd.
P # 3) Što je hrpa? Koje su njegove vrste?
Odgovor: Hrpa je hijerarhijska struktura podataka koja se temelji na stablu. Hrpa je kompletno binarno stablo. Hrpe su dvije vrste, tj. Max hrpa u kojoj je korijenski čvor najveći među svim čvorovima; Minimalna hrpa u kojoj je korijenski čvor najmanji ili najmanji među svim ključevima.
P # 4) Koje su prednosti Heap-a nad hrpom?
Odgovor: Glavna prednost hrpe nad stogom je u hrpi, memorija se dinamički raspoređuje i stoga nema ograničenja koliko memorije se može koristiti. Drugo, na stogu se mogu dodijeliti samo lokalne varijable dok na hrpi možemo dodijeliti i globalne varijable.
P # 5) Može li Heap imati duplikate?
Odgovor: Da, nema ograničenja u vezi s čvorovima s dupliciranim ključevima, jer je hrpa cjelovito binarno stablo i ne zadovoljava svojstva binarnog stabla pretraživanja.
Zaključak
U ovom uputstvu raspravljali smo o vrstama hrpe i sortiranju hrpe koristeći vrste hrpe. Također smo vidjeli detaljnu implementaciju njegovih vrsta u Javi.
=> Ovdje pogledajte Savršeni vodič za Java obuku.
Preporučena literatura
- Java Grafički priručnik - Kako implementirati strukturu podataka grafikona
- Uvod u strukture podataka na C ++
- Razvrstavanje hrpe u C ++ s primjerima
- Struktura podataka AVL stabla i hrpe u C ++
- Struktura podataka binarnog stabla u C ++
- Struktura podataka u redu čekanja u C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Osnove Java: Java sintaksa, Java klasa i osnovni koncepti Java
