what is heap data structure java
Acest tutorial explică ce este structura de date Java Heap și concepte conexe, cum ar fi Min Heap, Max Heap, Heap Sort, Stack vs Heap cu exemple:
O grămadă este o structură de date specială în Java. O grămadă este o structură de date bazată pe arbori și poate fi clasificată ca un arbore binar complet. Toate nodurile heap-ului sunt aranjate într-o ordine specifică.
=> Vizitați aici pentru a vedea seria de antrenament Java pentru toți
Ce veți învăța:
Structura de date Heap în Java
În structura de date heap, nodul rădăcină este comparat cu copiii săi și aranjat în conformitate cu ordinea. Deci, dacă a este un nod rădăcină și b este copilul său, atunci proprietatea, cheie (a)> = cheie (b) va genera un heap maxim.
Relația de mai sus dintre rădăcină și nodul copil este numită „Proprietate Heap”.
În funcție de ordinea nodurilor părinte-copil, heap-ul este în general de două tipuri:
# 1) Max-Heap :Într-un Max-Heap, cheia nodului rădăcină este cea mai mare dintre toate cheile din heap. Ar trebui să se asigure că aceeași proprietate este adevărată pentru toți subarborii din grămadă recursiv.
Diagrama de mai jos prezintă un Sample Max Heap. Rețineți că nodul rădăcină este mai mare decât copiii săi.
# 2) Min-Heap :În cazul unui Min-Heap, cheia nodului rădăcină este cea mai mică sau minimă dintre toate celelalte chei prezente în heap. Ca și în heap-ul Max, această proprietate ar trebui să fie adevărată recursiv în toate celelalte subarburi din heap.
Un exemplu, a unui copac Min-heap, este prezentat mai jos. După cum putem vedea, cheia rădăcină este cea mai mică dintre toate celelalte chei din heap.
O structură de date heap poate fi utilizată în următoarele zone:
- Grămezile sunt utilizate în principal pentru a implementa cozile prioritare.
- În special min-heap poate fi utilizat pentru a determina cele mai scurte căi între vârfurile dintr-un grafic.
Așa cum am menționat deja, structura de date heap este un arbore binar complet care satisface proprietatea heap pentru rădăcină și copii. Această grămadă este, de asemenea, numită ca grămadă binară .
Heap binar
O grămadă binară îndeplinește proprietățile de mai jos:
- O grămadă binară este un arbore binar complet. Într-un arbore binar complet, toate nivelurile, cu excepția ultimului nivel, sunt complet umplute. La ultimul nivel, tastele sunt cât mai departe posibil.
- Acesta satisface proprietatea heap. Heapul binar poate fi max sau min-heap în funcție de proprietatea heap pe care o satisface.
O grămadă binară este reprezentată în mod normal ca o matrice. Deoarece este un arbore binar complet, poate fi ușor reprezentat ca o matrice. Astfel, într-o reprezentare matrice a heap-ului binar, elementul rădăcină va fi A (0) unde A este matricea utilizată pentru a reprezenta heap-ul binar.
Deci, în general, pentru orice ianod în reprezentarea matricei heap binare, A (i), putem reprezenta indicii altor noduri așa cum se arată mai jos.
| A ((i-1) / 2) | Reprezintă nodul părinte |
|---|---|
| Accesul este mai rapid. | Mai lent decât teancul. |
| A ((2 * i) +1) | Reprezintă nodul copil stâng |
| A ((2 * i) +2) | Reprezintă nodul copil potrivit |
Luați în considerare următoarea grămadă binară:
Reprezentarea matricei heap-ului binar min de mai sus este după cum urmează:
Așa cum se arată mai sus, grămada este traversată conform ordinea nivelului adică elementele sunt traversate de la stânga la dreapta la fiecare nivel. Când elementele de la un nivel sunt epuizate, trecem la nivelul următor.
Apoi, vom implementa heap-ul binar în Java.
Programul de mai jos demonstrează heap-ul binar în 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 Ieșire:
nHeap = 7 4 6 1 3 2 5
Min Heap În Java
Un min-heap în Java este un arbore binar complet. În min-heap, nodul rădăcină este mai mic decât toate celelalte noduri din heap. În general, valoarea cheie a fiecărui nod intern este mai mică sau egală cu nodurile sale copil.
În ceea ce privește reprezentarea matricei min-heap, dacă un nod este stocat în poziția ‘i’, atunci nodul său stâng copil este stocat în poziția 2i + 1 și apoi nodul copil drept este în poziția 2i + 2. Poziția (i-1) / 2 își returnează nodul părinte.
Mai jos sunt enumerate diferitele operațiuni acceptate de min-heap.
# 1) Inserați (): Inițial, o nouă cheie este adăugată la capătul arborelui. Dacă cheia este mai mare decât nodul său părinte, atunci proprietatea heap este menținută. În caz contrar, trebuie să traversăm cheia în sus pentru a îndeplini proprietatea heap. Operațiunea de inserare în heap-ul minim necesită timp O (jurnal n).
# 2) extractMin (): Această operație elimină elementul minim din heap. Rețineți că proprietatea heap trebuie menținută după eliminarea elementului rădăcină (element min) din heap. Întreaga operație ia O (Logn).
# 3) getMin (): getMin () returnează rădăcina heap-ului, care este și elementul minim. Această operație se face în timp O (1).
Dat mai jos este un exemplu de arbore pentru un Min-heap.
Diagrama de mai sus arată un copac min-heap. Vedem că rădăcina arborelui este elementul minim din arbore. Deoarece rădăcina este la locația 0, copilul din stânga este plasat la 2 * 0 + 1 = 1 și copilul din dreapta este la 2 * 0 + 2 = 2.
Algoritm Min Heap
Dat mai jos este algoritmul pentru construirea unui min-heap.
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); } }Implementarea Min Heap în Java
Putem implementa min-heap folosind matrice sau cozi prioritare. Implementarea min-heap folosind cozi prioritare este implementarea implicită, deoarece o coadă prioritară este implementată ca min-heap.
Următorul program Java implementează min-heap-ul folosind Arrays. Aici folosim reprezentarea matricei pentru heap și apoi aplicăm funcția heapify pentru a menține proprietatea heap a fiecărui element adăugat la heap. În cele din urmă, afișăm heap-ul.
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()); } } Ieșire:
Max Heap în Java
Un heap maxim este, de asemenea, un arbore binar complet. Într-o grămadă maximă, nodul rădăcină este mai mare sau egal cu nodurile copil. În general, valoarea oricărui nod intern dintr-un heap maxim este mai mare sau egală cu nodurile sale copil.
În timp ce heapul maxim este mapat la o matrice, dacă vreun nod este stocat în poziția ‘i’, atunci copilul din stânga este stocat la 2i +1 și copilul din dreapta este stocat la 2i + 2.
Max-heap tipic va arăta așa cum se arată mai jos:
În diagrama de mai sus, vedem că nodul rădăcină este cel mai mare din heap și nodurile sale copil au valori mai mici decât nodul rădăcină.
Similar cu min-heap, heap-ul maxim poate fi reprezentat și ca o matrice.
Deci, dacă A este o matrice care reprezintă heap-ul Max, atunci A (0) este nodul rădăcină. În mod similar, dacă A (i) este orice nod din heap-ul maxim, atunci următoarele sunt celelalte noduri adiacente care pot fi reprezentate folosind o matrice.
- A ((i-1) / 2) reprezintă nodul părinte al lui A (i).
- A ((2i +1)) reprezintă nodul copil stâng al lui A (i).
- A (2i + 2) returnează nodul copil dreapta al lui A (i).
Operațiunile care pot fi efectuate pe Max Heap sunt date mai jos.
# 1) Inserați: Operația de inserare introduce o nouă valoare în arborele heap maxim. Se introduce la capătul copacului. Dacă noua cheie (valoare) este mai mică decât nodul său părinte, atunci proprietatea heap este menținută. În caz contrar, arborele trebuie să fie heapificat pentru a menține proprietatea heap.
întrebări și răspunsuri la interviu pentru Android pdf
Complexitatea în timp a operației de inserare este O (jurnal n).
# 2) ExtractMax: Operațiunea ExtractMax elimină elementul maxim (rădăcină) din heap-ul maxim. Operațiunea heapify, de asemenea, heap max pentru a menține proprietatea heap. Complexitatea în timp a acestei operații este O (log n).
# 3) getMax: Operația getMax returnează nodul rădăcină al heap-ului maxim cu complexitatea în timp a lui O (1).
Programul Java de mai jos implementează heap-ul maxim. Folosim ArrayList aici pentru a reprezenta elementele de heap max.
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); } } Ieșire:
Prioritate coadă min heap în Java
Structura de date a cozii prioritare în Java poate fi utilizată direct pentru a reprezenta min-heap-ul. În mod implicit, coada de prioritate implementează min-heap.
Programul de mai jos demonstrează min-heap-ul în Java utilizând coada prioritară.
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() + ' '); } } Ieșire:
Priority Queue Max Heap În Java
Pentru a reprezenta heap-ul maxim în Java folosind coada Priority, trebuie să folosim Collections.reverseOrder pentru a inversa min-heap-ul. Coada de prioritate reprezintă direct un min-heap în Java.
Am implementat Max Heap folosind o coadă prioritară în programul de mai jos.
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() + ' '); } } Ieșire:
Sortare în grămadă în Java
Sortarea Heap este o tehnică de sortare comparativă similară cu sortarea de selecție în care selectăm un element maxim din matrice pentru fiecare iterație. Sortarea Heap utilizează structura de date Heap și sortează elementele creând heap min sau max din elementele matrice care urmează a fi sortate.
Am discutat deja că în heap-ul min și max, nodul rădăcină conține elementul minim și respectiv maxim al matricei. În sortarea heap, elementul rădăcină al heap-ului (min sau max) este eliminat și mutat în matricea sortată. Heap-ul rămas este apoi heapified pentru a menține proprietatea heap.
Deci, trebuie să efectuați doi pași recursiv pentru a sorta matricea dată folosind sortarea heap.
- Construiți o grămadă din matricea dată.
- Scoateți în mod repetat elementul rădăcină din heap și mutați-l în matricea sortată. Heapify heap-ul rămas.
Complexitatea în timp a sortării Heap este O (n log n) în toate cazurile. Complexitatea spațială este O (1).
Algoritm de sortare în grămadă în Java
Dat mai jos sunt algoritmii de sortare heap pentru a sorta matricea dată în ordine crescătoare și descendentă.
# 1) Algoritm de sortare Heap pentru a sorta în ordine crescătoare:
- Creați o heap maximă pentru a fi sortată matricea dată.
- Ștergeți rădăcina (valoarea maximă în matricea de intrare) și mutați-o în matricea sortată. Plasați ultimul element în matrice la rădăcină.
- Heapify noua rădăcină a heap-ului.
- Repetați pașii 1 și 2 până când întregul tablou este sortat.
# 2) Algoritm de sortare Heap pentru a sorta în ordine descrescătoare:
- Construiți un Heap min pentru matricea dată.
- Eliminați rădăcina (valoarea minimă din matrice) și schimbați-o cu ultimul element din matrice.
- Heapify noua rădăcină a heap-ului.
- Repetați pașii 1 și 2 până când întregul tablou este sortat.
Implementarea sortării în heap în Java
Programul Java de mai jos folosește sortare heap pentru a sorta o matrice în ordine crescătoare. Pentru aceasta, mai întâi construim un heap maxim și apoi schimbăm recursiv și heapify elementul rădăcină așa cum este specificat în algoritmul de mai sus.
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)); } } Ieșire:
Complexitatea de timp generală a tehnicii de sortare a heap-ului este O (nlogn). Complexitatea în timp a tehnicii heapify este O (logn). În timp ce complexitatea timpului de construire a heap-ului este O (n).
Stack Vs Heap În Java
Să tabelăm acum câteva dintre diferențele dintre o structură de date Stack și o grămadă.
Grămadă Morman O stivă este o structură de date liniară. O grămadă este o structură ierarhică de date. Urmărește comanda LIFO (Last In, First Out). Traversal este în ordine de nivel. Cel mai utilizat pentru alocarea de memorie statică. Folosit pentru alocarea dinamică a memoriei. Memoria este alocată în mod contiguu. Memoria este alocată în locații aleatorii. Dimensiunea stivei este limitată în funcție de sistemul de operare. Sistemul de operare nu impune nicio limită pentru dimensiunea heap-ului. Stiva are acces doar la variabile locale. Heap are variabile globale alocate acestuia. Alocarea / repartizarea memoriei este automată. Alocarea / dealocarea trebuie făcută manual de către programator. Stiva poate fi implementată folosind Arrays, Linked List, ArrayList etc. sau orice alte structuri de date liniare. Heap este implementat folosind matrice sau copaci. Costul întreținerii, dacă este mai mic. Mai costisitor de întreținut. Poate duce la o lipsă de memorie, deoarece memoria este limitată. Nu există lipsă de memorie, dar poate suferi fragmentarea memoriei.
întrebări frecvente
Q # 1) Stiva este mai rapidă decât Heap?
Răspuns: O stivă este mai rapidă decât grămada, deoarece accesul este liniar în stivă comparativ cu grămada.
Q # 2) Pentru ce se folosește un Heap?
Răspuns: Heap este utilizat în cea mai mare parte în algoritmi care găsesc calea minimă sau cea mai scurtă între două puncte, cum ar fi algoritmul lui Dijkstra, pentru a sorta folosind sortarea heap, pentru implementări de coadă prioritare (min-heap) etc.
Î # 3) Ce este un Heap? Care sunt tipurile sale?
Răspuns: O grămadă este o structură de date ierarhizată, bazată pe copaci. O grămadă este un arbore binar complet. Greutățile sunt de două tipuri, adică heap-ul maxim în care nodul rădăcină este cel mai mare dintre toate nodurile; Min heap în care nodul rădăcină este cel mai mic sau minim dintre toate tastele.
Q # 4) Care sunt avantajele Heap față de un stack?
Răspuns: Avantajul major al heap-ului peste stivă este în heap, memoria este alocată dinamic și, prin urmare, nu există nicio limită pentru câtă memorie poate fi utilizată. În al doilea rând, numai variabilele locale pot fi alocate pe stivă, în timp ce putem aloca și variabile globale pe heap.
Q # 5) Poate Heap să aibă duplicate?
Răspuns: Da, nu există restricții pentru a avea noduri cu chei duplicate în grămadă, deoarece grămada este un arbore binar complet și nu îndeplinește proprietățile arborelui binar de căutare.
Concluzie
În acest tutorial, am discutat despre tipurile de heap și sortare heap folosind tipuri de heap. De asemenea, am văzut implementarea detaliată a tipurilor sale în Java.
=> Consultați aici Ghidul perfect de instruire Java.
Lectură recomandată
- Tutorial Java Graph - Cum se implementează structura datelor grafice
- Introducere în structurile de date în C ++
- Sortare în grămadă în C ++ cu exemple
- Structura de date AVB Tree și Heap în C ++
- Structura de date a arborelui binar în C ++
- Structura datelor în coadă în C ++ cu ilustrație
- Structură de date cu listă circulară în C ++ cu ilustrație
- Noțiuni de bază Java: Sintaxă Java, Java Class și Core Java Concepts
