Bago tayo magsimula, ipinapalagay na alam mo ang tungkol sa isang Binary Tree (sa isang binary tree, ang bawat node ay nag-iimbak ng isang susi na mas malaki kaysa sa lahat ng mga susi sa kaliwang subtree nito at mas mababa kaysa sa lahat ng mga susi sa kanang subtree nito ) . Samantalang, ang Binary Heap ay isang kumpletong binary tree na nakakatugon sa alinman sa min-heap o max-heap na pag-order na property. Kung hindi ka pamilyar sa mga konseptong ito, inirerekomenda namin sa iyo na maunawaan ang mga ito bilang isang kinakailangan. Maraming mga baguhang programmer ang nahihirapan sa konsepto ng Heaps, Min Heaps at Priority Queues. Sa post na ito, susuriin natin nang malalim para makita kung paano naiiba ang mga tambak sa Min-Heaps at kung paano natin magagamit ang Mga Priyoridad na Queue para Ipatupad ang Mga Min Heaps.
Ano ang Min Heap?
Ang isang min-heap ay may katangian na ang bawat node sa antas 'n' ay nag-iimbak ng isang halaga na mas mababa sa o katumbas ng mga anak nito sa antas na 'n+1'. Dahil ang ugat ay may halagang mas mababa o katumbas ng mga anak nito, na kung saan ay may mga halagang mas mababa o katumbas ng kanilang mga anak, iniimbak ng ugat ang pinakamababa sa lahat ng halaga sa puno.
Halimbawa
Figure 1: Isang simpleng min heap
Tandaan na walang kinakailangang relasyon sa pagitan ng halaga ng isang node at ng kapatid nito sa alinman sa min-heap o sa max-heap. Halimbawa, posible na ang mga halaga para sa lahat ng node sa kaliwang subtree ng ugat ay mas malaki kaysa sa mga halaga para sa bawat node ng kanang subtree.
Figure 2: Min heap na may kaliwang child node > right child node
Representasyon ng Min Heap sa Java
Ang pinakakaraniwang ginagamit na istraktura ng data upang kumatawan sa isang Min Heap ay isang simpleng Array. Bilang isang baguhan hindi mo kailangang lituhin ang isang "array" sa isang "min-heap". Maaari mong tingnan ito bilang, ang mga halaga ng mga node / elemento ng isang min-heap ay naka-imbak sa isang array . Tulad ng wala kaming anumang istraktura ng data upang mag-imbak ng isang " puno " sa Java at bumuo kami ng isang "node" para dito, o ang paraan ng paggamit namin ng "mapa" upang mag-imbak ng isang " graph ".
Figure 3: Array na representasyon ng Heap sa Figure 2
Ipapakita namin kung paano mo maa-access ang mga node ng magulang, kanan o kaliwang bata gamit ang mga sumusunod na formula.
Let minHeap[] ay isang integer array na may ugat sa index na “ i = 0; ”.
minHeap[(i - 1) / 2] ay nagbabalik ng parent node.
minHeap[(i * 2) + 2] ay nagbabalik ng tamang child node.
minHeap[(i * 2) + 1] ay nagbabalik ng kaliwang child node.
Isinasaalang-alang ang Figure # 2 na ibinigay sa itaas, ang halaga ng root (magulang) = 3, kaliwang child node ay 13 at kanang child node = 7.
Pagpapatupad ng Min Heap sa Java - Paggamit ng Mga Array
Tingnan natin ang pangunahing pagpapatupad ng Heaps gamit ang array, na may index bilang kasalukuyang posisyon ng elementong idaragdag, at laki bilang kabuuang sukat ng array.
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();
}
}
Output
Ang Min Heap ay : [3, 13, 7, 16, 21, 12, 9] Magulang : 3 Kaliwa : 13 Kanan :7 Magulang : 13 Kaliwa : 16 Kanan :21 Magulang : 7 Kaliwa : 12 Kanan :9 Ang Min na Halaga ay : 3 Ang Min Heap ay : [7, 13, 9, 16, 21, 12, 9] // pagkatapos tanggalin ang ugat Magulang : 7 Kaliwa : 13 Kanan :9 Magulang : 13 Kaliwa : 16 Kanan :21 Magulang : 9 Kaliwa: 12
Mga Priyoridad na Pila
Ang Priority Queue ay isang espesyal na uri ng pila kung saan ang bawat elemento ay nauugnay sa isang priyoridad at inilalagay ayon sa priyoridad nito. Para sa mas madaling pagpapatupad ng min heap, ginagamit namin ang PriorityQueue class na java.util.PriorityQueue na ibinigay ng Java. Kung ang mga ibinigay na elemento ay dapat na pinagbukud-bukod/ilalagay sa isang priyoridad pagkatapos ay isang Priority Queue ang gagamitin. Ang Priority Queue ay iba sa simpleng Queue dahil ang mga karaniwang queues ay sumusunod sa First-In-First-Out ( FIFO ) algorithm, ngunit kung minsan ang mga elemento ng queue ay kailangang iproseso ayon sa priority, kaya ang Priority Queue ay idinisenyo. Kapag nagdagdag ka ng mga elemento sa isang priyoridad na pila, ang isang min heap ay binuo bilang default.
Mga Karaniwang Operasyon
Bago tayo magpatuloy sa pagpapatupad narito ang ilang karaniwang operasyon sa java.util.PriorityQueue na kailangan mong malaman.
add(int element) ay naglalagay ng tinukoy na elemento sa isang priority queue.
remove(int element) ay nag-aalis ng isang instance ng tinukoy na elemento mula sa queue na ito, kung ito ay naroroon.
peek() kinukuha, ngunit hindi inaalis, ang ulo ng pila na ito, o nagbabalik ng null kung ang pila ay walang laman.
Kinukuha at inaalis ng poll() ang ulo ng pila na ito, o ibinabalik ang null kung walang laman ang pila na ito.
contains() ay nagbabalik ng "true" kung ang queue na ito ay naglalaman ng tinukoy na elemento.
size() ay nagbabalik ng bilang ng mga elemento sa priority queue/minheap na ito.
Pagpapatupad ng Min Heap sa Java gamit ang Priority Queues
Narito kung paano mo maipapatupad ang isang min heap gamit ang priority queue class ng 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);
}
}
Ang mga min heaps ay malawakang ginagamit upang kunin ang pinakamaliit na elemento sa isang pool ng mga elemento sa pare-parehong oras. Mayroong maraming iba pang mga application ng istraktura ng data na ito, gayunpaman maaari kang pumili ng anumang paraan upang ipatupad ito. Hindi na kailangang sabihin, kailangan mong magsanay nang may pasensya upang maging mahusay dito. Kaya't pasiglahin natin ang ating mga kalamnan at magtrabaho!
GO TO FULL VERSION