Heap Veri Yapısı

Bu rehberde, heap veri yapısının ne olduğunu öğreneceksiniz. Ayrıca c# dilinde kuyruk implementasyonunu göreceksiniz.

Heap veri yapısı, yığın özelliğini karşılayan eksiksiz bir ikili ağaçtır. Verilen düğüm

• her zaman alt düğümlerinden daha büyük ve ana düğümdeki anahtar diğer tüm düğünler arasında en büyüktür. Bu duruma max-heap denir.

• her zaman alt düğümlerinden daha küçük ve ana düğümdeki anahtar diğer tüm düğünler arasında en küçüktür. Bu duruma min-heap denir.

Bu veri yapısı ayrıca binary heap olarak da adlandırılır.

Heap İşlemleri#

Bir heap üzerinde gerçekleştirilen bazı önemli işlemler, algoritmaları ile birlikte aşağıda açıklanmıştır.

Heapify#

Heapify, ikili ağaçtan bir heap veri yapısı oluşturma işlemidir. Min-Heap veya Max-Heap oluşturmak için kullanılır.

1. Veri girişinden şöyle bir dizi alalım

2. Diziden tam bir ikili ağaç oluşturun

3. Dizini n/2 - 1 ile verilen yaprak olmayan düğümün ilk dizininden başlayın.

4. i mevcut elemanını en büyük olarak ayarlayın.

5. Sol alt düğümün indeksi 2i+1 ve sağ alt düğümün indeksi 2i+2 veriliyor.

• Eğer sol alt düğüm mevcut elemandan büyükse(Yani eleman i. indekste ise), leftChildIndex değişkenini en büyük olarak ayarlayın.

• Eğer sağ alt düğüm en büyükten büyükse(Yani eleman i. indekste ise), rightChildIndex değişkenini en büyük olarak ayarlayın.

6. En büyük ile mevcut elemanın yerlerini değiştirin.

7. Alt ağaçlar da yığın haline gelene (Heapify) kadar 3-7 arasındaki adımları tekrarlayın.

Heapify(array, size, i)
  EnBuyuk = i
  leftChild = 2i + 1
  rightChild = 2i + 2
  
  if leftChild > array[largest]
    EnBuyuk = leftChildIndex
  if rightChild > array[largest]
    EnBuyuk = rightChildIndex

  array[i] ile array[largest] elemanlarını yer değiştir

Max Heap oluşturmak için:

  MaxHeap(array, size)
    ilk indeksten alt düğümler bitene kadar döngü
      heapify metodunu çalıştır

Min-Heap için, hem leftChild hem rightChild tüm düğümler için üst düğümden daha küçük olmalıdır.

Heap Yapısına Eleman Ekleme#

Max-Heap yapısında eleman ekleme algoritması

If there is no node, 
  create a newNode.
else (a node is already present)
  insert the newNode at the end (last node from left to right)
  
heapify the array

1. Yeni elemanı ağacın sonuna yerleştirin.

2. Ağacı yığın haline getirin. (Heapify)

Min Heap için yukarıdaki algoritma, ana düğüm yeni düğümden her zaman küçük olacak şekilde değiştirilmiştir.

Heap Yapısından Eleman Silme#

Max Heap yapısında eleman silme algoritması

If nodeToBeDeleted is the leafNode
  remove the node
Else swap nodeToBeDeleted with the lastLeafNode
  remove noteToBeDeleted
   
heapify the array

1. Silinecek elemanı seçin.

2. Son eleman ile yer değiştirin.

3. Son elemanı silin.

4. Ağacı yığın haline getirin. (Heapify)

Min Heap için yukarıdaki algoritma, alt düğümler yeni düğümden küçük olacak şekilde değiştirilmiştir.

Göz Atma - Peek (Max-Min)#

Peek işlemi düğüm silmeden Max-Heap yapısından en büyük elemanı yada Min-Heap yapısından en küçük elemanı döndürür.

Max Heap ve Min Heap için

return AnaDugum

Çıkartma - Extract (Max-Min)#

Çıkart-Max, Max Heap yapısından maksimum değeri çıkardıktan sonra döndürüyorken Çıkart-Min ise Min Heap yapısından minimum değeri çıkardıktan sonra bu değeri döndürür.

C# Dilinde Heap Implementasyonu#

class Program
  {
      static void Main(string[] args)
      {
          List<int> array = new List<int>();
          int size = array.Count;

          Heap h = new Heap();
          h.insert(array, 3);
          h.insert(array, 4);
          h.insert(array, 9);
          h.insert(array, 5);
          h.insert(array, 2);

          Console.WriteLine("Öncelik Kuyruğu:\t");
          h.printArray(array);

          h.deleteNode(array, 4);
          Console.WriteLine("Eleman silindikten sonra kuyruk:\t");
          h.printArray(array);
      }
  }
public class Heap
{
    // Ağaç Yığınlaştırma
    public void heapify(List<int> hT, int i)
    {
        int size = hT.Count();
        // Kök, sağ ve sol düğümler arasından en büyüğünü bulma
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < size && hT[l] > hT[largest])
            largest = l;
        if (r < size && hT[r] > hT[largest])
            largest = r;
            
        // Eğer kök en büyük değilse yer değiştir ve yığınlaştırmaya devam et
        if (largest != i)
        { //Swap İşlemi
            int temp = hT[largest];
            hT[largest] = hT[i];
            hT[i] = temp;

            heapify(hT, largest);
        }
    }

    // Öncelik Kuyruğuna eleman ekleme
    public void insert(List<int> hT, int newNum)
    {
        int size = hT.Count();
        if (size == 0) { // Eleman yoksa direkt ekle
            hT.Add(newNum);
        }
        else // Eleman varsa ekle ve yığın haline getir
        {
            hT.Add(newNum);
            for (int i = size / 2 - 1; i >= 0; i--)
            {
                heapify(hT, i);
            }
        }
    }

    // Öncelik Kuyruğundan eleman silme
    public void deleteNode(List<int> hT, int num)
    {
        int size = hT.Count();
        int i;
        for (i = 0; i < size; i++)// Aranan elemanı bulma
        {
            if (num == hT[i])
                break;
        }
        //Swap işlemi
        int temp = hT[i];
        hT[i] = hT[size - 1];
        hT[size - 1] = temp;

        hT.Remove(size - 1);
        for (int j = size / 2 - 1; j >= 0; j--)//kaldırma sonrası yığın haline getirme
        {
            heapify(hT, j);
        }
    }

    // Eleman Yazdırma
    public void printArray(List<int> array)
    {
        foreach (int element in array)
        {
            Console.Write(element + " ");
        }
        Console.Write("\n");
    }
}

Heap Veri Yapısı Kullanımları#

• Öncelik Kuyruğu implementasyonunda

• Dijkstra Algoritmasında

• Heap Sıralamasında

Github'da bu sayfayı düzenle