Heapsort (Yığın Sıralaması)
Heapsort, bir dizindeki elemanları “heap” veri yapısını kullanarak sıralayan bir algoritmadır. O(n*log(n)) zaman karmaşıklığında çalışır. Heap veri yapısı ikili arama ağacına benzer bir yapıdadır. Max-heap ve Min-heap olmak üzere ikiye ayrılır. Max-heap’te yığın ağacındaki(heap) en büyük sayı her zaman en üsttedir(kök) ve ata düğümdeki değerler ondan sonra gelen çocuk düğümdeki değerlerden daha büyük olmak zorundadır. Min-heap ise bunun tam tersidir. En küçük eleman en üstte bulunur. Örnekle açıklayacak olursak:
4, 1, 3, 2, 16, 9, 10, 14, 8, 7 şeklinde bir ‘A’ dizinimiz olduğunu düşünelim. Bu dizinle bir max-heap oluşturacak olursak:
Max-heap’e bu şekilde yerleşeceklerdir. A[0]’ daki eleman ağacın köküdür. A[1]’deki eleman kökün solunda, A [2]’deki eleman ise kökün sağına yerleşti. Gördüğünüz gibi yığın ağacındaki maximum eleman kökte(root) durmaktadır. Peki bu heap veri yapısının avantajı nedir? Şöyle ki, yığın ağacındaki en büyük eleman root’ta olduğu için dizinin en büyük elemanına (veya min-heap kullanarak en küçük elemanına) ulaşmak çok hızlıdır(O(1) yani verimizin boyutu büyürken bu işlem hep aynı sürede gerçekleşir).
Peki heapsort nasıl uygulanır?
Heapsortu uygulayabilmek için iki yardımcı metoda ihtiyacımız var. Bunlardan ilki max-heapify() metodu(Min-heap için min-heapify() metodunu uyguluyoruz). Bu metod, verilen elemanın ağaçtaki yerini kontrol eder ve eğer yanlış yerdeyse onu yığın ağacında aşağılara doğru iterek doğru yere yerleşmesini sağlar. Örneğin aşağıdaki yığın ağacına bakalım. Max-heapify() metodundan ağacın ikinci düğümündeki değeri kontrol etmesini isteyelim.
2.düğümdeki değer(4), çocuk düğümlerden daha küçük(14 ve 7). O yüzden max-heapfiy() metodu ilk olarak 2. düğümü büyük olan çocuk düğümle(4.düğüm) yer değiştiricek ve onu bir aşağı levele itecek.
Metodumuz recursive olduğu için düğümün doğru yere yerleştiğine emin olana kadar sürekli kontrol edecek. Yukarıda görüldüğü gibi bir aşağı levele aldığımız düğüm yine max-heap kuralını ihlal ediyor(iki çocuk düğümden de büyük olmak zorunda). Bu yüzden metod yine çalışacak ve 4.düğümü büyük olan çocukla(9.düğüm) yer değiştirecek.
Ve artık elemanımız doğru yere yerleşti. Böylece 2.düğüm için çalıştırdığımız için max-heapify() metodu elemanı doğru yere yerleştirerek sonlanmış oldu.
Heapsort için ikinci yardımcı metodumuz is build-heap() metodu. Elimizde max-heapify() metodu olduğuna göre artık ağaçtaki tüm elemanlar için max-heapify() metodunu çağırıp elemanların doğru yere yerleştiğine emin olabiliriz. Tabi ki tüm düğümler için yapmak gereksiz olur çünkü yığın ağacındaki düğümlerin yarısının çocuk düğümü yok. Mesela 10 elemanlı bir yığın ağacı için 1'den 5'e kadar olan elemanlar için max-heapify() metodunu çağırmamız yeterli. En başta örnek olarak verdiğimiz A dizinine dönersek:
Build-heap() çağırmadan önceki yığın ağacının görüntüsü
Build-heap() metodu, 5.düğümden başlayıp kök düğüme kadar sıra sıra max-heapify() metodunu uygulayacak. Build-heap() çağırdıktan sonra:
Gördüğünüz gibi maximum eleman köke yerleşti ve aşağı doğru indikçe değerlerimiz küçülmeye başlıyor. A dizinimiz şu şekli aldı:
16, 14, 10, 8, 7, 9, 3, 2, 4, 1
build-heap() metodunu çağırarak neredeyse dizini büyükten küçüğe doğru dizmiş olduk. Bizim istediğimiz elemanların küçükten büyüğe doğru düzgün bir şekilde dizilmiş olması. Son olarak max-heapify() ve build-heap() metodlarını kullanarak heapsort algoritmamızı bitirmiş olacağız.
Heapsort() metodu, build-heap() metodunu çağırarak işe başlar. Böylece verilen A dizini için elimizde bir max-heap veri yapısı olur. (Yukarıdaki şekilde görüldüğü gibi). Bundan sonra yapmamız gereken şey, kökteki değerle ağacın son düğümündeki değerin yerini değiştirmek. Kökte en büyük değer olduğu için onu dizinin sonuna almış oluyoruz ve böylece olması gerektiği yerde konumlanmış oluyor.
16'yı en sona attık ve 1'i de en üste aldık. Köke aldığımız 1 değeri max-heap yapısını bozduğu için max-heapify() çağırıyoruz ve yukarıda gördüğünüz gibi 1 elemanını doğru yere yerleştiriyor. Tabi ki 16 değeri doğru yere yerleştiği için onu yığın ağacından kaldırıyoruz ve ağacın geri kalanı için yukarıda yaptığımız adımları tekrarlıyoruz. Özetle heapsort algoritması tek tek kökteki değerleri ağacın son düğümündeki değerle değiştiriyor ve bozulan max-heap yapısı için tekrar max-heapify() metodunu çağırıyor. Algoritma son adıma geldiği zaman(ağaçta tek bir eleman kaldığı zaman) görünüm bu şekilde olacak:
Böylece verilen A dizinini sıralamış olduk. Heap veri yapısının tek kullanım alanı heapsort değildir. Max-heap veya min-heap kullanılarak “Priority Queue” veri yapısını uygulayabiliriz. Bunu da başka bir yazıda anlatacağım.
Bu algoritmayı uygulayan java koduna bu linkten ulaşabilirsiniz. Algorithm/MaxHeapPriorityQueue.java at main · demirkirans/Algorithm (github.com)
KAYNAK
Introduction to Algorithms, 3rd Edition, Cormen et al.
Yığınlama Sıralaması (Heap Sort) — Bilgisayar Kavramları (bilgisayarkavramlari.com)
Heap Sort ( Yığın sıralaması ) Yapısı & Java’da Uygulanışı | Muslu.NET — Tayyip Muslu
