Yazan : Şadi Evren ŞEKER

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Yıpınlama sıralaması, arka planda bir yığın ağacı(heap) oluşturur ve bu ağacın en üstündeki sayıyı alarak sıralama işlemi yapar. (Lütfen yığın ağacındaki en büyük sayının her zaman en üstte duracağını hatırlayınız. )

Sıralanmak istenen verimiz:

5,12,20,18,4,3

olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Yukarıdaki bu sayılardan bir yığın ağacı oluşturulduğunda aşağıdaki şekilde bir sonuç elde edilir:

Bu ağacın en büyük değeri en üstte (kökte) durmaktadır öyleyse bu değer alınarak sonuç dizisinin son elemanı yapılırsa ve sonra geriye kalan sayılar tekrar yığınlanırsa (heapify) ve bu işlem eleman kalmayana kadar tekrarlanırsa sonuç dizisindeki veriler sıralanmış olarak elde edilir. Bu işlemler adım adım aşağıda gösterilmiştir:

Sonuç dizisi : {20}

20 sayısı yığın ağacından silindikten sonra kalan sayılar yığınlandıktan sonra yukarıdaki ağaç elde edilir. Bu ağacın en üstündeki sayı alınırsa sonuç dizisi : {20,18} olarak bulunur ve 18 alındıktan sonra kalan sayılar yığınlandığında ise aşağıdaki ağaç elde edilir.

Bu ağacında en üstünde bulunan sayı 12′dir ve bu sayı sonuç dizisine eklenir. Sonuç dizisi : {20,18,12} olarak bulunur ve kalan sayılar bir kere daha yığınlanır:

Sonuçta kalan sayıların yığınlanmasıyla yukarıdaki ağaç elde edilir ve bir kere daha en üstteki sayı alınarak sonuç dizisi : {20,18,12,5} olarak bulunur.

Aynı işlem kalan sayılara tekrar tekrar uygulanarak {20,18,12,5,4,3} sayıları elde edilir. Dikkat edilirse bu sayılar ilk başta verilen sayıların sıralanmış halidir. Şayet sıralama işlemi küçükten büyüğe yapılsın isteniyorsa bu durumda sayılar dizinin başından değil sonundan yazılarak kaydedilebilir veya çıkan sonuç tersten sıralanabilir.

Bu işlemi yapan bir yığın sıralaması (heap sort) kodu java dilinde aşağıdaki şekilde yazılabilir :

public void heapsort(int[]A){
    int tmp;
    BuildHeap(A);
    for(int i = A.length-1; i>=0; i--)
    {
     tmp=A[0];
     A[0]=A[i];
     A[i]=tmp;
     heapsize = heapsize -1 ;
     heapify(A,0);

    }
  }

Bu kodun diğer fonksiyonları için yığın ağacı (heap) başlıklı konuyu okuyabilirsiniz.