what is heap data structure java
Ta vadnica pojasnjuje, kaj je struktura podatkov Java Heap Data & s tem povezani koncepti, kot so Min Heap, Max Heap, Heap Sort, Stack vs Heap s primeri:
Kopica je posebna podatkovna struktura v Javi. Kopica je drevesna podatkovna struktura in jo lahko razvrstimo kot popolno binarno drevo. Vsa vozlišča kupa so razporejena v določenem vrstnem redu.
=> Obiščite tukaj, da si ogledate serijo Java Training for All
Kaj se boste naučili:
Struktura podatkov kopice v Javi
V strukturi podatkov kopice se korensko vozlišče primerja s svojimi podrejenimi elementi in je razvrščeno po vrstnem redu. Torej, če je a korensko vozlišče in b njegov podrejeni element, potem je lastnost, tipka (a)> = tipka (b) bo ustvaril največ kup.
Zgornja povezava med korenskim in podrejenim vozliščem se imenuje 'Lastnost kopice'.
Glede na vrstni red vozlišč staršev in otrok je kup na splošno dveh vrst:
# 1) Max-Heap :V Max-Heap-u je ključ korenskega vozlišča največji od vseh ključev na kupu. Zagotoviti je treba, da ista lastnost velja za vsa poddrevesa na kopici rekurzivno.
Spodnji diagram prikazuje vzorčni največji kup. Upoštevajte, da je korensko vozlišče večje od njegovih podrejenih.
# 2) Min-kup :V primeru Min-Heap je ključ korenskega vozlišča najmanjši ali najmanjši med vsemi drugimi ključi, ki so na kupu. Tako kot v Max heap-u, bi morala biti ta lastnost rekurzivno resnična v vseh ostalih poddrevesih na kopici.
Primer, drevesa Min-heap, je prikazano spodaj. Kot lahko vidimo, je korenski ključ najmanjši od vseh ostalih ključev na kupu.
Struktura podatkov kopice se lahko uporablja na naslednjih področjih:
- Gomile se večinoma uporabljajo za izvajanje prioritetnih čakalnih vrst.
- Zlasti min-heap lahko uporabimo za določanje najkrajših poti med točki v grafu.
Kot smo že omenili, je podatkovna struktura kopice popolno binarno drevo, ki izpolnjuje lastnost kopice za root in otroke. Ta kup se imenuje tudi kot binarni kup .
Binarni kup
Binarni kup izpolnjuje naslednje lastnosti:
- Binarna kopica je popolno binarno drevo. V celotnem binarnem drevesu so vse ravni, razen zadnje, popolnoma zapolnjene. Na zadnji ravni so tipke čim bolj levo.
- Izpolnjuje lastnost kopice. Binarna kopica je lahko max ali min-heap, odvisno od lastnosti kopice, ki jo izpolnjuje.
Binarni kup je običajno predstavljen kot matrika. Ker gre za popolno binarno drevo, ga lahko enostavno predstavimo kot matriko. Tako bo v matrični predstavitvi binarne kopice korenski element A (0), kjer je A matrika, ki se uporablja za predstavitev binarne kopice.
Torej na splošno za vsak ithvozlišče v binarni obliki matrike kopice A (i), lahko predstavljamo indekse drugih vozlišč, kot je prikazano spodaj.
| A ((i-1) / 2) | Predstavlja nadrejeno vozlišče |
|---|---|
| Dostop je hitrejši. | Počasnejši od sklada. |
| A ((2 * i) +1) | Predstavlja levo podrejeno vozlišče |
| A ((2 * i) +2) | Predstavlja desno podrejeno vozlišče |
Upoštevajte naslednji binarni kup:
Prikaz matrike zgornjega min binarnega kupa je naslednji:
Kot je prikazano zgoraj, se kopica prevozi po vrstni red torej se elementi prečkajo od leve proti desni na vsaki ravni. Ko so elementi na eni ravni izčrpani, preidemo na naslednjo stopnjo.
Nato bomo binarno kopico implementirali v Javo.
Spodnji program prikazuje binarni kup v 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 Izhod:
nHeap = 7 4 6 1 3 2 5
Min kup v Javi
Min-kup v Javi je popolno binarno drevo. V min-heap je korensko vozlišče manjše od vseh drugih vozlišč na kupu. Na splošno je ključna vrednost vsakega notranjega vozlišča manjša ali enaka njegovim podrejenim vozliščem.
Kar zadeva predstavitev polja min-heap, če je vozlišče shranjeno v položaju 'i', je njegovo levo podrejeno vozlišče shranjeno v položaju 2i + 1, nato pa je desno podrejeno vozlišče na položaju 2i + 2. Položaj (i-1) / 2 vrne nadrejeno vozlišče.
Spodaj so navedene različne operacije, ki jih podpira min-heap.
# 1) Vstavi (): Sprva se na koncu drevesa doda nov ključ. Če je ključ večji od nadrejenega vozlišča, se lastnost kopice ohrani. V nasprotnem primeru moramo ključ premakniti navzgor, da izpolnimo lastnost kopice. Postopek vstavljanja v min kup zahteva čas O (log n).
# 2) extractMin (): Ta operacija odstrani najmanjši element iz kupa. Upoštevajte, da je treba lastnost kopice ohraniti po odstranitvi korenskega elementa (min element) s kopice. Celotna operacija traja O (Logn).
# 3) getMin (): getMin () vrne koren kupa, ki je hkrati tudi najmanjši element. Ta postopek se izvede v O (1) času.
Spodaj je primer drevesa za Min-heap.
Zgornji diagram prikazuje drevo min kupe. Vidimo, da je koren drevesa najmanjši element v drevesu. Ker je koren na lokaciji 0, je njen levi podrejeni 2 * 0 + 1 = 1, desni pa 2 * 0 + 2 = 2.
Min kup algoritma
Spodaj je naveden algoritem za izdelavo min-kopice.
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); } }Izvajanje minimalne kopice v Javi
Min-heap lahko izvedemo bodisi z uporabo matrike ali prednostnih čakalnih vrst. Izvajanje min-heap z uporabo prioritetnih čakalnih vrst je privzeta izvedba, saj je prednostna vrsta implementirana kot min-heap.
Naslednji program Java izvaja min-heap s pomočjo nizov. Tu uporabljamo predstavitev matrike za kopico in nato uporabimo funkcijo heapify, da ohranimo lastnost kopice vsakega elementa, dodanega kopici. Na koncu prikažemo kup.
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()); } } Izhod:
Največ kup v Javi
Max kup je tudi popolno binarno drevo. V največjem kupu je korensko vozlišče večje ali enako podrejenim vozliščem. Na splošno je vrednost katerega koli notranjega vozlišča v največjem kupu večja ali enaka njegovim podrejenim vozliščem.
Medtem ko je največja kopica preslikana na matriko, če je katero koli vozlišče shranjeno na položaju 'i', se njegov levi podrejeni prostor shrani na 2i +1, desni podrejeni pa na 2i + 2.
Tipičen največji kup bo videti tako, kot je prikazano spodaj:
V zgornjem diagramu vidimo, da je korensko vozlišče največje na kopici, njegova podrejena vozlišča pa imajo vrednosti, manjše od korenskega vozlišča.
Podobno kot min-heap je tudi max kup mogoče predstaviti kot matriko.
Torej, če je A matrika, ki predstavlja največ kup, je A (0) korensko vozlišče. Podobno, če je A (i) katero koli vozlišče v največjem kupu, potem so naslednja druga sosednja vozlišča, ki jih je mogoče predstaviti z matriko.
- A ((i-1) / 2) predstavlja nadrejeno vozlišče A (i).
- A ((2i +1)) predstavlja levo podrejeno vozlišče A (i).
- A (2i + 2) vrne desno podrejeno vozlišče A (i).
Operacije, ki jih je mogoče izvesti na Max Heap, so podane spodaj.
# 1) Vstavi: Operacija vstavljanja vstavi novo vrednost v drevo največjega kupa. Vstavi se na koncu drevesa. Če je novi ključ (vrednost) manjši od nadrejenega vozlišča, se lastnost kopice ohrani. V nasprotnem primeru je treba drevo zložiti, da se ohrani lastnost kopice.
datoteke swf se ne predvajajo v brskalniku
Časovna zapletenost operacije vstavljanja je O (log n).
# 2) ExtractMax: Operacija ExtractMax odstrani največji element (koren) iz največjega kupa. Operacija prav tako zbere največ kup, da ohrani lastnost kopice. Časovna zapletenost te operacije je O (log n).
# 3) getMax: operacija getMax vrne korensko vozlišče največje kopice s časovno zahtevnostjo O (1).
Spodnji program Java izvaja največ kup. Tu uporabljamo ArrayList, da predstavljamo največ elementov kopice.
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); } } Izhod:
Minimalna vrsta prioritetne čakalne vrste v Javi
Strukturo podatkov prednostne čakalne vrste v Javi lahko neposredno uporabimo za predstavitev min-heap-a. Prednostna vrsta privzeto izvaja min-heap.
Spodnji program prikazuje min-kup v Javi z uporabo prednostne čakalne vrste.
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() + ' '); } } Izhod:
Najvišja količina prioritetne čakalne vrste v Javi
Za predstavitev največjega kopičenja v Javi s pomočjo čakalne vrste Priority moramo uporabiti Collections.reverseOrder za razveljavitev min-kopice. Prioritetna vrsta neposredno predstavlja min-kup v Javi.
Max Heap smo uvedli z vrsto prioritet v spodnjem 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() + ' '); } } Izhod:
Razvrsti kup na Javi
Razvrščanje kopice je primerjalna tehnika razvrščanja, podobna izbirni razvrstitvi, pri kateri za vsako ponovitev izberemo največ elementov v polju. Razvrščanje kopice uporablja strukturo podatkov kopice in razvršča elemente tako, da ustvari najmanjši ali največji kup iz elementov polja, ki jih je treba razvrstiti.
Že smo razpravljali, da v kopici min in max koreninsko vozlišče vsebuje najmanjši in največji element matrike. Pri razvrščanju kopice se koreninski element kupa (najmanjši ali največji) odstrani in premakne v razvrščeno polje. Preostali kup se nato zgosti, da se ohrani lastnost kupa.
Torej moramo narediti dva koraka rekurzivno za razvrščanje dane matrike s pomočjo heap sort.
- Iz dane matrike zgradite kopico.
- Večkrat odstranite korenski element s kopice in ga premaknite v razvrščeno matriko. Onesnažite preostali kup.
Časovna zapletenost sorte kopice je v vseh primerih O (n log n). Zapletenost prostora je O (1).
Algoritem razvrščanja kopice v Javi
Spodaj so algoritmi za razvrščanje kopice za razvrščanje dane matrike v naraščajočem in padajočem vrstnem redu.
# 1) Algoritem razvrščanja na kopico za razvrščanje po naraščajočem vrstnem redu:
- Ustvarite največji kup za razvrščeno dano polje.
- Izbrišite koren (največja vrednost v vnosnem polju) in ga premaknite v razvrščeno polje. Zadnji element v matriki postavite v koren.
- Onesnažite nov koren kupa.
- Ponavljajte koraka 1 in 2, dokler ni razvrščena celotna matrika.
# 2) Algoritem razvrščanja na kopico za razvrščanje po padajočem vrstnem redu:
- Sestavite min kup za dano matriko.
- Odstranite koren (najmanjša vrednost v polju) in ga zamenjajte z zadnjim elementom v polju.
- Onesnažite nov koren kupa.
- Ponavljajte koraka 1 in 2, dokler ni razvrščena celotna matrika.
Izvedba sortiranja kopice v Javi
Spodnji program Java uporablja sortiranje kopice za razvrščanje polja v naraščajočem vrstnem redu. Za to najprej izdelamo največjo kopico, nato pa rekurzivno zamenjamo in zgradimo korenski element, kot je določeno v zgornjem 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)); } } Izhod:
Skupna časovna zapletenost tehnike razvrščanja kopice je O (nlogn). Časovna zapletenost tehnike Heapify je O (logn). Medtem ko je časovna zapletenost gradnje kupa O (n).
Sestavite Vs kup v Javi
Oglejmo si zdaj tabelarizacijo nekaterih razlik med strukturo podatkovnega sklada in kupom.
Stack Kup Sklop je linearna podatkovna struktura. Kup je hierarhična struktura podatkov. Sledi naročanju LIFO (zadnji vstop, prvi izhod). Prehod poteka po ravnem. Večinoma se uporablja za statično dodeljevanje pomnilnika. Uporablja se za dinamično dodeljevanje pomnilnika. Spomin se dodeli sočasno. Pomnilnik je dodeljen na naključnih mestih. Velikost skladov je omejena glede na operacijski sistem. Brez omejitev velikosti kopice, ki jo določa operacijski sistem. Stack ima dostop samo do lokalnih spremenljivk. Kup ima dodeljene globalne spremenljivke. Dodelitev / sprostitev pomnilnika je samodejna. Dodelitev / sprostitev mora programer opraviti ročno. Sklop je mogoče implementirati z uporabo nizov, povezanega seznama, seznama ArrayList itd. Ali katere koli druge linearne podatkovne strukture. Kup se izvaja z uporabo nizov ali dreves. Stroški vzdrževanja, če so manjši. Dražje za vzdrževanje. Lahko povzroči pomanjkanje pomnilnika, ker je pomnilnik omejen. Pomnilnika ne primanjkuje, vendar lahko trpi zaradi razdrobljenosti spomina.
Pogosto zastavljena vprašanja
V # 1) Ali je sklad hitrejši od kupa?
Odgovor: Sklop je hitrejši od kopice, saj je dostop do njega v primerjavi s kopico linearni.
V # 2) Za kaj se uporablja kup?
Odgovor: Kopiček se večinoma uporablja v algoritmih, ki najdejo najmanjšo ali najkrajšo pot med dvema točkama, kot je Dijkstrin algoritem, za razvrščanje s pomočjo sortiranja kopice, za izvedbe prednostne čakalne vrste (min-heap) itd.
V # 3) Kaj je kup? Katere so njegove vrste?
Odgovor: Kup je hierarhična, na drevesu temelječa podatkovna struktura. Kup je popolno binarno drevo. Kupi so dveh vrst, tj. Največja kopica, pri kateri je korensko vozlišče največje med vsemi vozlišči; Min kup, pri katerem je korensko vozlišče najmanjše ali najmanjše med vsemi ključi.
V # 4) Kakšne so prednosti kopičenja pred kupom?
Odgovor: Glavna prednost kopičenja v kupu je v kopici, pomnilnik se dinamično dodeli in zato ni omejitve glede količine pomnilnika. Drugič, v sklad je mogoče dodeliti samo lokalne spremenljivke, medtem ko lahko na kupu določimo tudi globalne spremenljivke.
V # 5) Ali ima Heap dvojnike?
Odgovor: Da, ni omejitev, da bi na kupu imeli vozlišča s podvojenimi ključi, saj je kup celotno binarno drevo in ne izpolnjuje lastnosti binarnega drevesa iskanja.
Zaključek
V tej vadnici smo razpravljali o vrstah kupa in razvrščanju kopice z uporabo vrst kupa. Opazili smo tudi podrobno izvajanje njegovih vrst v Javi.
=> Tukaj si oglejte Perfect Java Training Guide.
Priporočeno branje
- Vadnica za grafe Java - Kako uporabiti strukturo podatkov grafov
- Uvod v podatkovne strukture v jeziku C ++
- Razvrstitev kopice v C ++ z primeri
- Struktura podatkov drevesa in kopice AVL v jeziku C ++
- Struktura podatkov binarnega drevesa v jeziku C ++
- Struktura podatkov čakalne vrste v jeziku C ++ z ilustracijo
- Struktura podatkov krožnega povezanega seznama v jeziku C ++ z ilustracijo
- Osnove Java: Sintaksa Java, Razred Java in Osnovni koncepti Java
