Î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.
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
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
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 ”.
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.
Fie minHeap[] este un tablou întreg cu rădăcină la indicele „ i = 0; ”.
Având în vedere figura #2 prezentată mai sus, valoarea rădăcinii (părinte) = 3, nodul copil stâng este 13 și nodul copil drept = 7.
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();
}
}
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);
}
}
Min heaps sunt utilizate pe scară largă pentru a recupera cel mai mic element dintr-un grup de elemente în timp constant. Există o mulțime de alte aplicații ale acestei structuri de date, totuși puteți alege orice metodă pentru a implementa acest lucru. Inutil să spun că trebuie să exersezi cu răbdare pentru a te pricepe la asta. Așa că haideți să ne punem mușchii în mișcare și să trecem la treabă!
GO TO FULL VERSION