Yazan : Şadi Evren ŞEKER

Yığın ağacı bilgisayar bilimlerinde özellikle sıralama amacıyla çokca kullanılan bir veri yapısıdır. Bu veri yapısı üst düğümün (atasının) alt düğümlerden (çocuklarından) her zaman büyük olduğu bir ikili ağaç (binary tree) şeklinde düşünülebilir.

Aşağıda örnek bir yığın ağacı verilmiştir:

Yukarıdaki ikili ağaçta dikkat edilirse ağaç dengeli bir şekilde sırayla doldurulmuştur. Buna göre yeni bir eleman daha eklenmesi durumunda ağacın eleman sayısı 7′ye yükselecek ve sayıların yeri değişmekle birlikte yeni eleman şu andaki 18 sayısını içeren düğümün sağına gelecektir.

Yığın ağaçları her zaman sırayla dolar ve sırayla boşalır.

Yukarıdaki ağacın bir dizi ile tutulması da mümkündür.

Ayrıca herhangi bir ağacı yığın ağacına çevirmek (yığınlamak, heapify) de mümkündür ve bu işlem bir yığın ağacı oluşturma işleminin temelini oluşturur. Basitçe yığın ağacına yapılan her ekleme ve her çıkarma işleminden sonra bu yığınlama (heapify) işlemi yapılarak yığın ağacının formunu koruması sağlanmalıdır.

Aşağıda java dilinde bir yığınlama (heapify) fonksiyonu verilmiştir:

public void heapify(int[]A,int i)
  {
        int largest = 0;
    int le=left(i);
    int ri=right(i);
    if((le<=heapsize) && (A[le]>A[i]))
        largest = le;
    else
        largest = i;
    if((ri<=heapsize) && A[ri]>A[largest])
        largest = ri;

    if (largest != i) {
      int tmp = A[i];
      A[i]= A[largest];
      A[largest] = tmp;
      heapify(A, largest);
   }
  }
  public static int left(int i ){
      return 2*(i+1)-1;
  }

  public static int right(int i){
      return 2*(i+1);
  }

Dolayısıyla yukarıdaki yığınlama (heapify) fonksiyonu kullanarak bir yığın ağacı oluşturmak aşağıdaki şekildem mümkün olabilir:

public void BuildHeap(int[]A){

  heapsize=A.length-1;
  for(int i=0; i<Math.floor(A.length/2); i++)
  {
          heapify(A,i);
  }
}