Înainte de a începe, se presupune că știți despre un arbore binar (într-un arbore binar, fiecare nod stochează o cheie mai mare decât toate cheile din subarborele din stânga și mai puțin decât toate cheile din subarborele din dreapta ) . Întrucât, un heap binar este un arbore binar complet care satisface fie proprietatea de ordonare min-heap , fie max-heap. Dacă nu sunteți familiarizat cu aceste concepte, vă recomandăm să le înțelegeți ca o condiție prealabilă. Mulți programatori începători se pot lupta cu conceptul de Heaps, Min Heaps și Priority Queues. În această postare, vom face o scufundare profundă pentru a vedea cum diferă heap-urile de Min-Heaps și cum putem folosi Priority Queues pentru a implementa Min Heaps.
Figura 1: Un simplu heap min
Rețineți că nu există o relație necesară între valoarea unui nod și cea a fratelui său, fie în heap-ul min sau în heap-ul maxim. De exemplu, este posibil ca valorile pentru toate nodurile din subarborele din stânga al rădăcinii să fie mai mari decât valorile pentru fiecare nod din subarborele din dreapta.
Figura 2: Heap min cu noduri secundare din stânga > noduri secundare din dreapta
Figura 3: Reprezentarea matrice a Heap-ului din Figura 2
Vom demonstra cum puteți accesa pur și simplu nodurile părinte, dreapta sau stânga folosind următoarele formule.
Ce este un Min Heap?
Un min-heap are proprietatea că fiecare nod de la nivelul „n” stochează o valoare care este mai mică sau egală cu cea a copiilor săi la nivelul „n+1”. Deoarece rădăcina are o valoare mai mică sau egală cu copiii săi, care la rândul lor au valori mai mici sau egale cu copiii lor, rădăcina stochează minimul tuturor valorilor din arbore.Exemplu
![Min Heap în Java cu exemple - 2](https://cdn.codegym.cc/images/article/d23087ba-4f7e-4c70-9291-801e2ea4cf80/512.jpeg)
![Min Heap în Java cu exemple - 3](https://cdn.codegym.cc/images/article/c4096755-00d8-4634-9406-7a220172c264/512.jpeg)
Reprezentarea Min Heap în Java
Structura de date cel mai frecvent utilizată pentru a reprezenta un Min Heap este un simplu Array. Ca începător, nu trebuie să confundați o „matrice” cu un „heap min”. Vă puteți uita la el ca valorile nodurilor / elementelor unui min-heap sunt stocate într-o matrice . La fel cum nu avem nicio structură de date pentru a stoca un „ arbore ” în Java și construim un „nod” pentru acesta, sau modul în care folosim „hartă” pentru a stoca un „ grafic ”.![Min Heap în Java cu exemple - 4](https://cdn.codegym.cc/images/article/37b326ea-5df1-456f-bf36-c3b023b064c9/512.jpeg)
- Fie minHeap[] este un tablou întreg cu rădăcină la indicele „ i = 0; ”.
- minHeap[(i - 1) / 2] returnează nodul părinte.
- minHeap[(i * 2) + 2] returnează nodul copil potrivit.
- minHeap[(i * 2) + 1] returnează nodul copil stâng.
Implementarea Min Heap în Java - Utilizarea Arrays
Să ne uităm la implementarea de bază a Heaps folosind matrice, cu index ca poziție curentă a elementului de adăugat și dimensiunea ca dimensiune totală a matricei.import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
Ieșire
Heap-ul minim este: [3, 13, 7, 16, 21, 12, 9] Părinte: 3 Stânga: 13 Dreapta:7 Părinte: 13 Stânga: 16 Dreapta:21 Părinte: 7 Stânga: 12 Dreapta:9 Valoarea minimă este : 3 Min Heap este : [7, 13, 9, 16, 21, 12, 9] // după îndepărtarea rădăcinii Părinte : 7 Stânga : 13 Dreapta :9 Părinte : 13 Stânga : 16 Dreapta :21 Părinte : 9 Stânga: 12
Cozi prioritare
O coadă de prioritate este un tip special de coadă în care fiecare element este asociat cu o prioritate și este plasat în funcție de prioritatea sa. Pentru o implementare mai ușoară a heap-ului min, folosim clasa PriorityQueue java.util.PriorityQueue furnizată de Java. Dacă elementele date ar trebui să fie sortate/plasate într-o prioritate, atunci se folosește o coadă de prioritate. O coadă cu prioritate este diferită de o coadă simplă, deoarece cozile standard urmează algoritmul First-In-First-Out ( FIFO ), dar uneori elementele cozii trebuie procesate în funcție de prioritate, de aceea este proiectată Priority Queue. Când adăugați elemente la o coadă de prioritate, se construiește în mod implicit un heap min.Operațiuni comune
Înainte de a trece la implementare, iată câteva operațiuni comune în java.util.PriorityQueue pe care trebuie să le cunoașteți.- add(int element) inserează elementul specificat într-o coadă de prioritate.
- remove(int element) elimină o singură instanță a elementului specificat din această coadă, dacă este prezent.
- peek() preia, dar nu elimină, capul acestei cozi sau returnează null dacă coada este goală.
- poll() preia și elimină capul acestei cozi, sau returnează null dacă această coadă este goală.
- contains() returnează „adevărat” dacă această coadă conține elementul specificat.
- size() returnează numărul de elemente din această coadă de prioritate/minheap.
Implementarea Min Heap în Java folosind Cozile prioritare
Iată cum puteți implementa un heap min folosind clasa de coadă de prioritate prin java.import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
Ieșire
minHeap.add(3) = 3 minHeap.view() = 3 13 7 16 21 12 9 minHeap.peek() = 3 minHeap.poll() = 7 13 9 16 21 12 minHeap.remove(7) = 9 13 12 16 21 minHeap.contains(11) = fals minHeap.contains(16) = adevărat