Mielőtt elkezdenénk, feltételezzük, hogy ismer egy bináris fát (egy bináris fában minden csomópont tárol egy kulcsot, amely nagyobb , mint a bal oldali részfájának összes kulcsa , és kisebb , mint a jobb részfa összes kulcsa ) . Míg a bináris kupac egy teljes bináris fa, amely kielégíti a min-heap vagy a max-heap rendezési tulajdonságot. Ha nem ismeri ezeket a fogalmakat, javasoljuk, hogy előfeltételként ismerje meg ezeket. Sok kezdő programozó küzdhet a kupacok, a minimális kupacok és a prioritási sorok koncepciójával. Ebben a bejegyzésben alaposan meglátjuk, miben különböznek a kupacok a Min-Heap-től, és hogyan használhatjuk a prioritási sorokat a minimális kupacok megvalósítására.
Mi az a Min Heap?
A min-halomnak az a tulajdonsága, hogy minden 'n' szintű csomópont olyan értéket tárol, amely kisebb vagy egyenlő, mint az 'n+1' szintű gyermekei értéke. Mivel a gyökér értéke kisebb vagy egyenlő, mint a gyermekei, amelyek viszont kisebbek vagy egyenlők a gyermekeikkel, a gyökér az összes érték minimumát tárolja a fában.
Példa
1. ábra: Egyszerű min kupac
Megjegyzendő, hogy nincs szükség kapcsolat egy csomópont és testvére értéke között sem a min-halomban, sem a max-heap-ben. Például lehetséges, hogy a gyökér bal oldali részfájában lévő összes csomópont értéke nagyobb, mint a jobb oldali részfa minden csomópontjának értéke.
2. ábra: Minimális kupac bal oldali gyermekcsomópontokkal > jobb gyermekcsomópontokkal
A Min Heap ábrázolása Java nyelven
A Min Heap ábrázolására leggyakrabban használt adatstruktúra egy egyszerű tömb. Kezdőként nem kell összetévesztenie a „tömböt” a „min-heap-el”. Megnézheti úgy, hogy egy min-halom csomópontjainak / elemeinek értékei egy tömbben vannak tárolva . Ugyanúgy, ahogy nincs adatszerkezetünk a „ fa ” tárolására a Java-ban, és egy „csomópontot” építünk hozzá, vagy ahogyan a „térképet” használjuk a „ grafikonok ” tárolására.
3. ábra: A kupac tömbábrázolása a 2. ábrán
Bemutatjuk, hogyan érheti el egyszerűen a szülő, jobb vagy bal gyermek csomópontokat a következő képletekkel.
Legyen a minHeap[] egy egész tömb, amelynek a gyökér indexe „ i = 0; ”.
minHeap[(i - 1) / 2] a szülőcsomópontot adja vissza.
A minHeap[(i * 2) + 2] a megfelelő gyermekcsomópontot adja vissza.
minHeap[(i * 2) + 1] a bal oldali gyermekcsomópontot adja vissza.
Figyelembe véve a fenti 2. ábrát, a gyökér (szülő) értéke = 3, a bal gyermekcsomópont értéke 13, a jobb gyermekcsomópont = 7.
Min Heap implementációja Java nyelven – tömbök használata
Nézzük meg a Heaps tömb használatával történő alapvető megvalósítását, ahol az index a hozzáadandó elem aktuális pozíciója, a méret pedig a tömb teljes mérete.
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();
}
}
Kimenet
A minimális halom: [3, 13, 7, 16, 21, 12, 9] Szülő : 3 Bal : 13 Jobb :7 Szülő : 13 Bal : 16 Jobb :21 Szülő : 7 Bal : 12 Jobb :9 A minimális érték a következő: 3 A Min Heap: [7, 13, 9, 16, 21, 12, 9] // a gyökér eltávolítása után Szülő : 7 Bal : 13 Jobb :9 Szülő : 13 Bal : 16 Jobb :21 Szülő : 9 Balra: 12
Elsőbbségi sorok
A Priority Queue egy speciális várólista, amelyben minden elem prioritáshoz van rendelve, és a prioritása szerint kerül elhelyezésre. A min heap egyszerűbb megvalósításához a Java által biztosított java.util.PriorityQueue PriorityQueue osztályt használjuk . Ha az adott elemeket prioritásba kell rendezni/elhelyezni, akkor Priority Queue-t használunk. A Priority Queue különbözik az egyszerű Queue-tól, mert a szabványos sorok a First-In-First-Out ( FIFO ) algoritmust követik, de néha a sor elemeit prioritás szerint kell feldolgozni, ezért került kialakításra a Priority Queue. Amikor elemeket ad hozzá egy prioritási sorhoz, alapértelmezés szerint egy minimális kupac épül fel.
Közös műveletek
Mielőtt rátérnénk a megvalósításra, itt van néhány gyakori művelet a java.util.PriorityQueue fájlban , amelyeket tudnia kell.
Az add(int elem) beszúrja a megadott elemet egy prioritási sorba.
Az remove(int element) eltávolítja a megadott elem egyetlen példányát a sorból, ha az jelen van.
A peek() lekéri, de nem távolítja el ennek a sornak a fejét, vagy nullát ad vissza, ha a sor üres.
A poll() lekéri és eltávolítja ennek a sornak a fejét, vagy nullát ad vissza, ha ez a sor üres.
A include() „true”-t ad vissza, ha ez a sor tartalmazza a megadott elemet.
A size() a prioritási sor/minheap elemeinek számát adja vissza.
A Min Heap megvalósítása Java-ban prioritási sorok használatával
Az alábbiakban bemutatjuk, hogyan valósíthat meg egy minimális kupacot a java prioritási sorosztályával.
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);
}
}
A minimális kupacokat széles körben használják egy elemkészlet legkisebb elemének állandó időben történő lekérésére. Ennek az adatszerkezetnek számos más alkalmazása is létezik, de ennek megvalósításához bármilyen módszert választhat. Mondanom sem kell, türelemmel kell gyakorolnod, hogy jó legyen. Mozgassuk tehát az izmainkat és kezdjünk dolgozni!
GO TO FULL VERSION