Başlamadan önce, bir İkili Ağaç hakkında bilgi sahibi olduğunuz varsayılmaktadır (ikili ağaçta her düğüm, sol alt ağacındaki tüm anahtarlardan daha büyük ve sağ alt ağacındaki tüm anahtarlardan daha az bir anahtar depolar ) . Oysa İkili Yığın , min-yığın veya maksimum-yığın sıralama özelliğini karşılayan tam bir ikili ağaçtır.. Bu kavramlara aşina değilseniz, bunları bir ön koşul olarak anlamanızı öneririz. Birçok acemi programcı, Yığınlar, Min Yığınlar ve Öncelik Sıraları kavramlarıyla mücadele edebilir. Bu gönderide yığınların Min-Yığınlardan ne kadar farklı olduğunu ve Min Yığınları Uygulamak için Öncelik Sıralarını nasıl kullanabileceğimizi görmek için derin bir dalış yapacağız.
Min Yığın nedir?
Bir min yığını, 'n' seviyesindeki her düğümün, 'n+1' seviyesindeki çocuklarından daha küçük veya ona eşit bir değer saklama özelliğine sahiptir. Kök, çocuklarından küçük veya onlara eşit bir değere sahip olduğundan, onlar da çocuklarından küçük veya onlara eşit değerlere sahip olduğundan, kök, ağaçtaki tüm değerlerin minimumunu depolar.
Örnek
Şekil 1: Basit bir minimum yığın
Min-heap veya max-heap'teki bir düğümün değeri ile kardeşinin değeri arasında gerekli bir ilişki olmadığına dikkat edin. Örneğin, kökün sol alt ağacındaki tüm düğümlerin değerlerinin, sağ alt ağacın her düğümünün değerlerinden büyük olması mümkündür.
Şekil 2: Sol alt düğümler > sağ alt düğümler ile minimum yığın
Min Heap'in Java'da Temsili
Min Yığını temsil etmek için en sık kullanılan veri yapısı basit bir Dizidir. Yeni başlayan biri olarak, bir "diziyi" bir "min-yığın" ile karıştırmanıza gerek yoktur. Buna bir min-heap'in düğümlerinin / öğelerinin değerlerinin bir dizide saklandığı şeklinde bakabilirsiniz . Tıpkı Java'da bir " ağacı " depolamak için herhangi bir veri yapımız olmaması ve bunun için bir "düğüm" oluşturmamız veya bir " grafik " depolamak için "haritayı" kullanma şeklimiz gibi.
Şekil 3: Şekil 2'deki Heap'in dizi gösterimi
Aşağıdaki formülleri kullanarak ebeveyn, sağ veya sol alt düğümlere nasıl kolayca erişebileceğinizi göstereceğiz.
MinYığın [] , kökü “ i = 0; ”.
minYığın[(i - 1) / 2] üst düğümü döndürür.
minYığın[(i * 2) + 2] sağ alt düğümü döndürür.
minYığın[(i * 2) + 1], sol alt düğümü döndürür.
Yukarıda verilen Şekil # 2 dikkate alındığında kök (ebeveyn) = 3, sol alt düğüm 13 ve sağ alt düğüm = 7'dir.
Java'da Min Heap Uygulaması - Dizileri Kullanma
Eklenecek öğenin geçerli konumu indeks ve dizinin toplam boyutu olarak boyut olmak üzere dizi kullanan Heaps'in temel uygulamasına bakalım.
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();
}
}
Çıktı
En Az Yığın : [3, 13, 7, 16, 21, 12, 9] Ebeveyn : 3 Sol : 13 Sağ :7 Ebeveyn : 13 Sol : 16 Sağ :21 Ebeveyn : 7 Sol : 12 Sağ :9 Minimum Değer is : 3 Min Yığın : [7, 13, 9, 16, 21, 12, 9] // kökü kaldırdıktan sonra Ebeveyn : 7 Sol : 13 Sağ :9 Ebeveyn : 13 Sol : 16 Sağ :21 Ebeveyn : 9 Sol : 12
Öncelik Sıraları
Öncelik Sırası, her öğenin bir öncelik ile ilişkilendirildiği ve önceliğine göre yerleştirildiği özel bir sıra türüdür . Min yığının daha kolay uygulanması için Java tarafından sağlanan PriorityQueue sınıfını java.util.PriorityQueue kullanıyoruz . Verilen öğelerin bir önceliğe göre sıralanması/yerleştirilmesi gerekiyorsa, bir Öncelik Kuyruğu kullanılır. Öncelik Kuyruğu, basit Kuyruktan farklıdır çünkü standart kuyruklar İlk Giren İlk Çıkar ( FIFO ) algoritmasını izler, ancak bazen sıranın öğelerinin önceliğe göre işlenmesi gerekir, bu nedenle Öncelik Kuyruğu tasarlanmıştır. Öğeleri bir öncelik kuyruğuna eklediğinizde, varsayılan olarak bir min yığın oluşturulur.
Ortak İşlemler
Uygulamaya geçmeden önce, burada java.util.PriorityQueue'de bilmeniz gereken birkaç genel işlem var.
add(int öğesi), belirtilen öğeyi bir öncelik sırasına ekler.
remove(int element), eğer varsa, belirtilen elemanın tek bir örneğini bu sıradan kaldırır.
peek() bu kuyruğun başını alır, ancak kaldırmaz veya sıra boşsa null değerini döndürür.
poll() bu kuyruğun başını alır ve kaldırır veya bu sıra boşsa null değerini döndürür.
Bu sıra belirtilen öğeyi içeriyorsa, içerir () "true" değerini döndürür.
size(), bu öncelik sırası/min yığınındaki öğelerin sayısını döndürür.
Min Heap'in Java'da Priority Queues kullanılarak uygulanması
Java tarafından öncelikli sıra sınıfını kullanarak bir min yığınını nasıl uygulayabileceğiniz aşağıda açıklanmıştır.
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 yığınları, bir öğe havuzundaki en küçük öğeyi sabit zamanda almak için yaygın olarak kullanılır. Bu veri yapısının birçok başka uygulaması vardır, ancak bunu uygulamak için herhangi bir yöntemi seçebilirsiniz. Söylemeye gerek yok, bunda iyi olmak için sabırla pratik yapmalısınız. O halde hadi kaslarımızı hareket ettirelim ve işe koyulalım!
GO TO FULL VERSION