Heap Veri Yapısı: Heap Nedir? Min ve Maks Yığın (Örnek)

Yığın Nedir?

Yığın, özel bir ağaç veri yapısıdır. Yığın, kök (ebeveyn) adı verilen en üst düğümden oluşur. İkinci çocuğu kökün sol çocuğu iken, üçüncü düğüm kökün sağ çocuğudur. Ardışık düğümler soldan sağa doğru doldurulur. Ebeveyn düğüm anahtarı, yavrularının anahtarıyla karşılaştırılır ve uygun bir düzenleme gerçekleşir. Her bir varlığa düğüm adı verildiği için ağacı görselleştirmek kolaydır. Düğümün tanımlama için benzersiz anahtarları vardır.

Neden Yığın Veri Yapısına ihtiyacınız var?

Yığın Veri Yapısını kullanmanın ana nedenleri şunlardır:

Yığın veri yapısı logaritmik zamanda silme ve eklemeye izin verir – O(log₂N).
Ağaçtaki veriler belirli bir sıraya göre oluşturulur. Programcı, maksimum veya minimum gibi şeyleri güncellemenin veya sorgulamanın yanı sıra ebeveyn ile yavru arasındaki ilişkileri de bulabilir.
konseptini uygulayabilirsiniz. Belge Nesnesi Modeli yığın veri yapısını anlamanıza yardımcı olmak için.

Yığın Türleri

Yığın veri yapısı, bir yığın veri yapısındaki eklemeleri işlemek ve öğeleri kaldırmak için Öncelik Sırası, İkili Yığın, Binom Yığın ve dahil olmak üzere çeşitli algoritmalara sahiptir. Yığın Sıralama.

Öncelik Sırası: Öncelikli nesneleri içeren soyut bir veri yapısıdır. Her nesnenin veya öğenin kendisi için önceden düzenlenmiş bir önceliği vardır. Bu nedenle, daha yüksek öncelik verilen nesne veya öğe, hizmeti diğerlerinden önce alıyor.
İkili Yığın: İkili yığınlar, silme ve ekleme gibi basit yığın işlemleri için uygundur.
Binom-Yığın: Binom yığını, yığını oluşturan bir dizi binom ağacı koleksiyonundan oluşur. Binom Heap ağacı, titizlikle tanımlandığı gibi sıradan bir ağaç değildir. Binom ağacındaki toplam eleman sayısı her zaman 2'ye sahiptirⁿ düğümleri.
Yığın Sıralaması: Çoğu sıralama algoritmasının aksine yığın sıralama, sıralama işlemi için O(1) alanını kullanır. Sıralamanın önce maksimum yığına dönüştürülerek artan sırada gerçekleştiği, karşılaştırmaya dayalı bir sıralama algoritmasıdır. Yığın Sıralamasına yükseltilmiş kalitede bir ikili arama ağacı olarak bakabilirsiniz.

Tipik olarak bir yığın veri yapısı iki strateji kullanır. Giriş 12 – 8 – 4 – 2 ve 1 için

Min Heap – en üstteki değer
Max Heap – en üstteki en yüksek değer

Min Yığın

Min Heap yapısında kök düğüm, o düğümdeki çocuklara eşit veya onlardan daha küçük bir değere sahiptir. Min Heap'in bu yığın düğümü minimum değeri tutar. Sonuçta minimum yığın yapısı tam bir ikili ağaç.

Bir ağaçta bir Min yığını oluşturduğunuzda, tüm yapraklar uygun adaylardır. Ancak tam Max-heap değerini elde etmek için yaprakların her birini incelemeniz gerekir.

Minimum Yığın Örneği

Yukarıdaki diyagramlarda kökten en alt düğüme kadar net bir sıralama görebilirsiniz.

Elemanları Array_N[12,2,8,1,4] dizininde depoladığınızı varsayalım. Dizide görebileceğiniz gibi, kök eleman Min Heap önceliğini ihlal ediyor. Min heap özelliğini korumak için, Min heap özellikleri karşılanana kadar elemanları değiştirmek için min-heapify işlemlerini gerçekleştirmeniz gerekir.

Maksimum Yığın

Max Heap'in yapısında, ebeveyn veya kök düğüm, düğümdeki çocuklarına eşit veya onlardan daha büyük bir değere sahiptir. Bu düğüm maksimum değeri tutar. Üstelik bu tam bir ikili ağaçtır, dolayısıyla bir değerler koleksiyonundan maksimum bir yığın oluşturabilir ve onu O(n) zamanında çalıştırabilirsiniz.

Java max yığınını uygulamak için birkaç yöntem:

Eklemek (): yığına yeni bir öğe yerleştirin. Bir dizi kullanıyorsanız nesneler dizinin sonuna eklenir; ikili ağaçta ise nesneler yukarıdan aşağıya ve sonra soldan sağa eklenir.
Kaldırmak (): Bu yöntem, ilk öğeyi dizi listesinden kaldırmanıza olanak tanır. Yeni eklenen öğe artık en büyüğü olmadığından, Sift-Down yöntemi onu her zaman yeni konumuna iter.
Aşağı Eleme (): Bu yöntem kök nesneyi onun alt nesnesiyle karşılaştırır ve ardından yeni eklenen düğümü hak ettiği konuma iter.
Yukarı Eleme (): Bir diziye yeni eklenen bir öğe eklemek için dizi yöntemini kullanırsanız, Sift-Up yöntemi yeni eklenen düğümün yeni konumuna taşınmasına yardımcı olur. Yeni eklenen öğe ilk olarak ağaç veri yapısını simüle ederek üst öğeyle karşılaştırılır.
Parent_Index=Child_Index/2 formülünü uygulayın. Maksimum eleman dizinin önüne gelene kadar bunu yapmaya devam edersiniz.

Temel Yığın Operaleri

Bir veri kümesindeki en yüksek ve en düşük değerleri bulmanız için bulma, silme ve ekleme gibi birçok temel yığın işlemine ihtiyacınız vardır. Öğeler sürekli gelip gideceğinden şunları yapmanız gerekir:

bulmak – Bir yığının içindeki bir öğeyi arayın.
Ekle – Yığına yeni bir çocuk ekleyin.
Sil – Bir yığından bir düğümü silin.

Yığınlar Oluştur

Yığın oluşturma işlemi yığın oluşturma olarak bilinir. Bir anahtar listesi verildiğinde, programcı boş bir yığın oluşturur ve ardından temel yığın işlemlerini kullanarak diğer anahtarları birer birer ekler.

Öyleyse Willaim'in yöntemini kullanarak 12,2,8,1 ve 4 değerlerini bir yığına ekleyerek bir Min-yığın oluşturmaya başlayalım. Boş bir yığınla başlayıp ardından O (nlogn) süresini kullanarak bunu diğer öğelerle art arda doldurarak n öğeli yığın oluşturabilirsiniz.

Heapify: bir yığına elemanlar eklemeye yardımcı olan ekleme algoritmasında. Özellik yığın veri yapısının vurgulanıp vurgulanmadığını kontrol eder.
Örneğin, bir max heapify, ebeveynin değerinin yavrularından büyük olup olmadığını kontrol eder. Daha sonra öğeler takas gibi yöntemler kullanılarak sıralanabilir.

Birleştirme: Birleştirmek için iki yığınınız olduğunu göz önünde bulundurarak, iki yığındaki değerleri bir araya getirmek için birleştirme yığınlarını kullanın. Ancak orijinal yığınlar hala korunmaktadır.

Yığınları İncele

Yığınların İncelenmesi, yığın veri yapısındaki öğelerin sayısının kontrol edilmesi ve yığının boş olup olmadığının doğrulanması anlamına gelir.

Yığınları öğelerin sıralanması veya sıralanması olarak incelemek önemlidir. Is-Empty() kullanarak işlenecek öğeleriniz olup olmadığını kontrol etmek önemlidir. Yığın boyutu, maksimum yığını veya minimum yığını bulmanıza yardımcı olacaktır. Bu nedenle, yığın özelliğini takip eden öğeleri bilmeniz gerekir.

Boyut – yığının büyüklüğünü veya uzunluğunu döndürür. Kaç öğenin sıralı düzende olduğunu söyleyebilirsiniz.
Boş – eğer yığın NULL ise TRUE, aksi halde FALSE döndürür.

Burada, dosyadaki tüm öğeleri yazdırıyorsunuz. öncelikQ döngü ve ardından öncelikQ'nun boş olmadığını kontrol etmek.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Yığın Veri Yapısının Kullanım Alanları

Yığın veri yapısı, gerçek hayattaki birçok programlama uygulamasında aşağıdakiler gibi faydalıdır:

Spam Filtrelemede yardımcı olur.
Grafik algoritmalarının uygulanması.
OperaSistem yükü dengeleme ve veri sıkıştırma.
İstatistiklerdeki sırayı bulun.
Bir listedeki öğeleri logaritmik zamanda arayabileceğiniz Öncelik kuyruklarını uygulayın.
Yığın veri yapısı aynı zamanda sıralama için de kullanılır.
Müşterileri bir hat üzerinde simüle etmek.
İşlemeyi kesme OperaZamanlama Sistemi.
Huffman'ın veri sıkıştırma kodlamasında.

Yığın Önceliği Sırası Özellikleri

Öncelik yığınlarında, listedeki veri öğeleri daha küçük olan öğeyi belirlemek için birbirleriyle karşılaştırılır.
Bir öğe bir kuyruğa yerleştirilir ve daha sonra kaldırılır.
Öncelik Kuyruğundaki her bir öğenin, öncelik olarak tanımlanan, kendisiyle ilgili benzersiz bir numarası vardır.
Öncelik Kuyruğundan çıkıldığında, en yüksek öncelikli öğe ilk önce çıkar.

Yığın Önceliği Sırasını uygulamaya yönelik adımlar Java

Kod Örneği ile JAVA'da Yığın Sıralaması

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Çıktı

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Yığın Sıralama Python Kod Örneği ile

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)