Sadurunge miwiti, dianggep sampeyan ngerti babagan Wit Binar (ing wit binar, saben simpul nyimpen kunci sing luwih gedhe tinimbang kabeh tombol ing subtree kiwa lan kurang saka kabeh tombol ing subtree tengen ) . Dene, Binary Heap minangka wit binar lengkap sing nyukupi properti pesenan min-heap utawa max-heap.. Yen sampeyan ora ngerti konsep kasebut, disaranake sampeyan ngerti iki minangka prasyarat. Akeh programer pemula bisa berjuang karo konsep Heaps, Min Heaps lan Antrian Prioritas. Ing kirim iki, kita bakal nyilem jero kanggo ndeleng kepiye tumpukan beda karo Min-Heaps lan kepiye carane nggunakake Antrian Prioritas kanggo Ngleksanakake Min Heaps.
Apa Min Heap?
Tumpukan min nduweni properti yen saben simpul ing level 'n' nyimpen nilai sing kurang saka utawa padha karo anak-anake ing level 'n+1'. Amarga oyod nduweni nilai kurang saka utawa padha karo anak-anake, sing banjur duwe nilai kurang saka utawa padha karo anak-anake, oyod nyimpen minimal kabeh nilai ing wit.
Tuladha
Gambar 1: Tumpukan min prasaja
Elinga yen ora ana hubungan sing perlu antarane nilai simpul lan sedulure ing min-heap utawa max-heap. Contone, bisa uga nilai kanggo kabeh simpul ing subtree kiwa saka ROOT luwih gedhe tinimbang nilai kanggo saben simpul saka subtree tengen.
Gambar 2: Heap min karo node anak kiwa > simpul anak tengen
Representasi Min Heap ing Jawa
Struktur data sing paling umum digunakake kanggo makili Min Heap yaiku Array sing prasaja. Minangka pamula sampeyan ora perlu bingung "array" karo "min-numpuk". Sampeyan bisa ndeleng minangka, nilai node / unsur saka min-numpukan disimpen ing array . Kaya kita ora duwe struktur data kanggo nyimpen " wit " ing Jawa lan kita mbangun "simpul" kanggo iku, utawa cara kita nggunakake "peta" kanggo nyimpen " grafik ".
Gambar 3: Representasi array saka Heap ing Gambar 2
Kita bakal nduduhake carane sampeyan bisa ngakses simpul anak induk, tengen utawa kiwa kanthi nggunakake rumus ing ngisor iki.
Ayo minHeap[] minangka array integer kanthi ROOT ing indeks " i = 0; ”.
minHeap [(i - 1) / 2] ngasilake simpul induk.
minHeap [(i * 2) + 2] ngasilake simpul anak tengen.
minHeap [(i * 2) + 1] ngasilake simpul anak kiwa.
Ngelingi Gambar # 2 ing ndhuwur, nilai root (induk) = 3, simpul anak kiwa yaiku 13 lan simpul anak tengen = 7.
Implementasi Min Heap ing Jawa - Nggunakake Array
Ayo kang katon ing implementasine dhasar saka Heaps nggunakake array, karo indeks minangka posisi saiki saka unsur sing bakal ditambahake, lan ukuran minangka ukuran total Uploaded.
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();
}
}
Antrian Prioritas minangka jinis antrian khusus sing saben unsur digandhengake karo prioritas lan diselehake miturut prioritas. Kanggo implementasine luwih gampang saka tumpukan min, kita nggunakake PriorityQueue kelas java.util.PriorityQueue diwenehake dening Jawa. Yen unsur sing diwenehi mestine diurutake / dilebokake ing prioritas banjur Antrian Prioritas digunakake. Antrian Prioritas beda karo antrian sing prasaja amarga antrian standar ngetutake algoritma First-In-First-Out ( FIFO ), nanging kadhangkala unsur-unsur antrian kudu diproses miturut prioritas, mula antrian Prioritas dirancang. Yen sampeyan nambahake unsur menyang antrian prioritas, tumpukan min dibangun kanthi gawan.
Operasi Umum
Sadurunge kita nerusake kanggo implementasine kene sawetara operasi umum ing java.util.PriorityQueue sing kudu ngerti.
nambah (unsur int) nglebokake unsur kasebut ing antrian prioritas.
mbusak (unsur int) mbusak Kayata siji saka unsur kasebut saka antrian iki, yen saiki.
Ndeleng () retrieves, nanging ora mbusak, sirah antrian iki, utawa bali null yen antrian kosong.
jajak pendapat () retrieves lan mbusak sirah antrian iki, utawa bali null yen antrian iki kosong.
ngandhut () ngasilake "bener" yen antrian iki ngemot unsur kasebut.
size () ngasilake nomer unsur ing antrian prioritas iki / minheap.
Implementasi Min Heap ing Jawa nggunakake Priority Queues
Mangkene carane sampeyan bisa ngetrapake tumpukan min nggunakake kelas antrian prioritas dening 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);
}
}
Tumpukan min akeh digunakake kanggo njupuk unsur paling cilik ing blumbang unsur ing wektu pancet. Ana akeh aplikasi liyane saka struktur data iki, nanging sampeyan bisa milih cara kanggo ngleksanakake iki. Ora perlu ngomong, sampeyan kudu latihan kanthi sabar supaya bisa dadi apik. Dadi ayo otot-otot kita obah lan bisa kerja!
GO TO FULL VERSION