Yığın Veri Yapısı: Yığın Nedir?

Yığın Veri Yapısı Nedir?

Yığın (Heap), özel bir ağaç tabanlı veri yapısıdır. Yığın veri yapısı, kök (ebeveyn) adı verilen en üstteki düğümden oluşur. İkinci düğüm, kökün sol çocuğu, üçüncü düğüm ise kökün sağ çocuğudur. Ardışık düğümler soldan sağa doğru doldurulur. Ebeveyn düğümünün anahtarı, uygun bir düzenleme oluşması için yavrularının anahtarıyla karşılaştırılır. Ağacı görselleştirmek kolaydır; her varlık bir düğüm olarak adlandırılır ve her düğümün tanımlanması için benzersiz bir anahtarı vardır.

Basitçe ifade etmek gerekirse, bir Heap, heap özelliğini sağlayan eksiksiz bir ikili ağaçtır: her ebeveyn, çocuklarına göre tutarlı bir şekilde sıralanmıştır; bu da onu öncelik kuyrukları ve Heap Sort için ideal kılar.

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

İşte yığın (heap) kullanmanın başlıca nedenleri:

• Yığın veri yapısı, silme ve ekleme işlemlerini logaritmik sürede (O(log)) gerçekleştirir.₂N).
• Ağaç yapısındaki veriler belirli bir düzende sıralanmıştır. Programcı, maksimum veya minimum gibi değerleri güncellemenin veya sorgulamanın yanı sıra, üst öğe ile alt öğe arasındaki ilişkileri de bulabilir.
• konseptini uygulayabilirsiniz. Belge Nesnesi Modeli Yığın Veri Yapısını görsel olarak anlamanıza yardımcı olmak için.
• Yığınlar, Dijkstra'nın en kısa yol algoritması ve Prim'in minimum yayılma ağacı gibi grafik algoritmaları için kritik öneme sahip olan verimli öncelik kuyruğu işlemlerini destekler.

Yığın Türleri

Yığın veri yapısı, öncelik kuyruğu, ikili yığın, binom yığın ve benzeri çeşitli algoritmalar kullanarak eleman ekleme ve çıkarma işlemlerini yönetir. Yığın Sıralama.

• Öncelik Sırası: Bu bir abstracÖnceliklendirilmiş nesneleri içeren bir veri yapısı. Her nesne veya öğe için önceden belirlenmiş bir öncelik vardır. Bu nedenle, daha yüksek önceliğe sahip olan nesne veya öğe, diğerlerinden önce hizmet alır.
• İkili Yığın: İkili yığınlar, silme ve ekleme gibi basit yığın işlemleri için uygundur. Çoğu standart kütüphane öncelik kuyruğunun arkasındaki varsayılan uygulamadır.
• İkili Yığın: Binom yığını, yığını oluşturan bir dizi binom ağacı koleksiyonundan oluşur. Binom yığını ağacı, kesin olarak tanımlandığı için sıradan bir ağaç değildir. Bir binom ağacındaki toplam eleman sayısı her zaman 2'ye eşittir.ⁿ düğümleri.
• Yığın Sıralama: Çoğu sıralama algoritmasının aksine, Yığın Sıralama (Heap Sort) sıralama işlemi için O(1) alan kullanır. Girişi önce bir Maksimum Yığına (Max-Heap) dönüştürerek artan sırada sıralamanın gerçekleştiği karşılaştırma tabanlı bir sıralama algoritmasıdır. Yığın Sıralamayı, geliştirilmiş bir ikili arama ağacı olarak düşünebilirsiniz.

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

• Min-Yığın – en düşük değer en üstte
• Maksimum Yığın – en yüksek değer en üstte

Min-Yığın

Min-Heap yapısında, kök düğümün değeri, o düğümün çocuklarının değerine eşit veya onlardan daha küçüktür. Bu nedenle, bir Min-Heap'in kökü minimum değeri tutar. Min-Heap aynı zamanda tam bir ikili ağaçtır.

Bir ağaçta minimum yığın (Min-Heap) oluşturduktan sonra, tüm yapraklar maksimum değer için uygun adaylardır. Ancak, tam maksimum yığın değerini elde etmek için her bir yaprağı incelemeniz gerekir.

Minimum Yığın Örneği

Yukarıdaki diyagramda, kökten en alt düğüme doğru açık bir sıralama olduğunu görebilirsiniz.

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

Maksimum Yığın

Max-Heap yapısında, üst veya kök düğümün değeri, çocuklarının değerine eşit veya onlardan daha büyüktür. Bu düğüm en büyük değeri tutar. Tam bir ikili ağaç olduğundan, bir Max-Heap'i O(n) sürede bir değer koleksiyonundan oluşturabilirsiniz.

İşte bir uygulamanın hayata geçirilmesinde yaygın olarak kullanılan birkaç yöntem. Java Maksimum Yığın:

• Eklemek (): Yığına yeni bir eleman ekler. Dizi kullanıyorsanız, nesneler dizinin sonuna eklenir; ikili ağaçta ise nesneler yukarıdan aşağıya ve ardından soldan sağa doğru eklenir.
• Kaldırmak (): Bu yöntem, dizi listesinden ilk öğeyi kaldırmanıza olanak tanır. Yeni eklenen öğe artık en büyük öğe olmadığı için, Sift-Down yöntemi onu her zaman yeni konumuna iter.
• Sift-Down (): Bu yöntem, kök nesneyi alt nesneleriyle karşılaştırır ve ardından yeri değiştirilen düğümü doğru konumuna iter.
• Eleme (): Eğer bir diziye yeni bir öğe eklemek için dizi yöntemini kullanırsanız, Sift-Up yöntemi yeni eklenen düğümün doğru konumuna yeniden yerleştirilmesine yardımcı olur. Yeni öğe, ağaç veri yapısı simüle edilerek önce ebeveyniyle karşılaştırılır.

  Parent_Index = Child_Index / 2 formülünü uygulayın. En büyük eleman dizinin başına gelene kadar bu işlemi tekrarlayın.

Temel Yığın Operaleri

Bir veri kümesindeki en yüksek ve en düşük değerleri bulmak için, bulma, ekleme ve silme gibi birkaç temel yığın işlemine ihtiyacınız vardır. Elemanlar sürekli olarak gelip gittiği için şunları bilmeniz 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şlemine yığın oluşturma denir. Programcı, verilen bir anahtar listesiyle boş bir yığın oluşturur ve ardından temel yığın işlemlerini kullanarak diğer anahtarları tek tek ekler.

Şimdi William'ın yöntemini kullanarak 12, 2, 8, 1 ve 4 değerlerini ekleyerek bir Min-Heap oluşturmaya başlayalım. Boş bir yığınla başlayıp ardından diğer elemanlarla sırayla doldurarak n elemanlı bir yığın oluşturabilirsiniz; bu işlem O(n log n) zaman alır.

• Heapify: Yığın özelliğini koruyarak yığına eleman eklemeye yardımcı olan bir ekleme rutini.

  Örneğin, bir max-heapify işlemi, üst öğenin değerinin alt öğeden daha büyük olup olmadığını kontrol eder. Ardından, öğeler swap gibi yöntemler kullanılarak sıralanabilir.ping.

• Birleştirme: İki yığını birleştirmek istediğinizde, iki yığındaki değerleri bir araya getirmek için birleştirme işlemini kullanın. Orijinal yığınlar korunmaya devam eder.

Yığınları İncele

Yığınları incelemek, yığın veri yapısındaki eleman sayısını kontrol etmeyi ve yığının boş olup olmadığını doğrulamayı ifade eder.

Elemanları sıralarken veya kuyruğa alırken yığınları incelemek önemlidir. Is-Empty() kullanarak işlenecek eleman olup olmadığını kontrol etmek önemlidir. Yığın boyutu, Max-Heap veya Min-Heap köklerini bulmaya yardımcı olur, bu nedenle yığın özelliğini kaç elemanın izlediğini bilmeniz gerekir.

• Beden – Yığın boyutunu veya uzunluğunu döndürür. Sıralı halde kaç elemanın saklandığını gösterir.
• Boş – Yığın boşsa 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 kullanışlıdır, örneğin:

• İstenmeyen mesajları filtrelemeye yardımcı olur.
• Dijkstra ve Prim gibi grafik algoritmalarının uygulanması.
• OperaSistem yük dengelemesi ve veri sıkıştırma.
• k-inci en küçük eleman gibi sıralama istatistiklerini bulmak.
• Öncelik kuyrukları uygulayarak, bir listedeki öğeleri logaritmik sürede arayabilirsiniz.
• Yığın veri yapısı, yığın sıralama algoritması aracılığıyla sıralama için de kullanılır.
• Bekleme sırasındaki müşterileri simüle etmek.
• Kesme işlemlerinin yönetimi OperaZamanlama Sistemi.
• Huffman kodlamasında veri sıkıştırma kullanılır.
• Yapay zekâ tabanlı yol planlamasında en iyi ilk arama ve A* sezgisel algoritmalarını destekliyor.

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

Aşağıdaki özellikler, yığın üzerinde oluşturulan öncelik kuyruğunun nasıl davrandığını açıklamaktadır:

• Öncelikli yığınlarda, listedeki veri öğeleri birbirleriyle karşılaştırılarak daha küçük veya daha büyük olan öğe belirlenir.
• Bir öğe kuyruğa yerleştirilir ve daha sonra öncelik sırasına göre kaldırılır.
• Öncelik kuyruğundaki her bir öğenin, öncelik olarak tanımlanan benzersiz bir numarası vardır.
• Öncelik kuyruğundan çıkıldığında, en yüksek önceliğe sahip öğe ilk önce çıkar.

Yığın Öncelik Kuyruğunun Uygulanmasına İlişkin Adımlar Java

Sonraki bölüm somut konulara geçiyor. Java Bu kuralları çalışan koda dönüştüren uygulama.

Yığın Sıralama Java 'da Code Örnek E-posta

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 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 'da Code Örnek E-posta

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)

Çıktı

[1, 3, 4, 7, 9]

Sonraki bölümde şunlar hakkında bilgi edineceksiniz: İkiye Bölme Yöntemi.

SSS