Yığınlama Sıralaması (Heap Sort)
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.
İlk ağaç şemasında zaten nerdeyse tüm dizi sıralanmış ahlde duruyor. Aslı mesele dizin o ağaç şekline naısl geldiği ?
Yukarıdaki bu yazı sadece yığın sıralamasını (heap sort) açıklamaktadır. Yazının içerisinde de bağlantı (link) olduğu üzere, yığının oluşturulması
http://bilgisayarkavramlari.com/2008/08/09/yigin-agaci-heap/
Yukarıdaki yazıda açıklanmıştır.
başarılar
ben c de linked list sıralamk ve ekrana yazdırmak istiyorum.bunun için nasıl bir kod yazmak gerekiyor?
Bu yorumu yazdığınız, yığın ağaçları (heap) konusu, sadece diziler üzerinde sıralama yapılması için tasarlanmıştır. Zaten yığın ağaçlarının özelliği, dizi üzerinden kolay kullanılabilmesidir.
Sorunuza cevap için bağlı liste ve sıralama algoritmalarının anlatıldığı aşağıdaki başlıkları okumanızda yarar olabilir:
Sitede anlatılan sıralama algoritmalarının tam listesi için:
http://www.bilgisayarkavramlari.com/2007/05/03/linked-list-linkli-liste-veya-bagli-liste/
Bağlı listeler üzerinde yazılan örnek kodlar için:
http://www.bilgisayarkavramlari.com/2008/08/09/siralama-algoritmalari-sorting-algorithms/
Ayrıca aşağıdaki bağlantıdan, geçen dönem ticart üniversitesinde verdiğim veri yapıları ve algoritmalar dersine ve bu derste yazılan kodlara erişebilirsiniz:
http://www.sadievrenseker.com/vy/
Yukarıdaki bu bağlantılarda aradığınız konuyu bulamazsanız, daha fazla detay vermeniz halinde yardımcı olacak bir kod yazıp sitede yayınlamaya çalışırım.
başarılar
mehaba sayın hocam. heap sort un mantıgı en büyük sayı en üstte olmalı. Fakat şöyle bir soruda mantık yürütemedim.
bunlardan hangisi heap yapısını temsil eder deniliyor.
22 79 36 89 80 91 42 53 96
22 36 79 42 91 80 96 53 89
22 36 89 42 91 80 96 53 79
burda nasıl bir yöntem izlemeliyim.
Heap yapısı max heap veya min heap olarak ikiye ayrılır. Max heap yapısında en büyük sayı hep en üstte dururken min heap yapısında, en küçük sayı hep en üstte durur. Amaca göre seçim yapılır. Örneğin küçükten büyüğe sıralama için min heap , büyükten küçüğe doğru sıralama için max heap kullanılır.
Sizin sorunuzda, min heap kullanılmış. Bu durumda doğru cevap ikinci dizilim oluyor. Bunun dışındaki dizilimlerde üstte bulunan sayı küçük olması gerekirken büyük olmuş.
başarılar
ben hala anlamış değilim bu kümeleme ağacı neye göre oluşturuluyor yardımcı olursanız sevinirim
20 sayısı çıkarıldıktan sonra ağaç tekrar yığınlanmış mesela 4 ile 5 in yeri değiştirilse herhangi bir sorun olur mu?birde siteyi pek araştırma imkanım olmadı ama mesela bu kümeleme ağacını oluşturma algoritmasının c kodları ile yazılmış olanı var mı?
Yukarıdaki yazının ilk satırında da bağlantı olduğu üzere sorunuzun cevabı Heap (Yığın) başlıklı yazıda verilmiştir. Ayrıca bu yazıda bir kod da bulunmaktadır. Yukarıdaki yazı oluşturulmuş bir yığının sıralama için kullanılmasını anlatmaktadır. Bir yığının nasıl oluşturulacağı (heapify) ise Heap (Yığın) başlıklı yazıda yer alıyor. İlgili yazıya aşağıdaki bağlantıdan ulaşabilirsiniz.
http://bilgisayarkavramlari.com/2008/08/09/yigin-agaci-heap/
başarılar
hocam ben heap dizilişlerini dizinin indisleri kullanılarak yaptım.
burda bir şekil üzerinde 3 tane heap yapısının dizilimini gerçekleştirdim.
1.dizim de indis sayısı 7 olan 53 sayısı parent(89) dan küçük oldugun için dizilişi bozar.
2.dizimde indis sıralama küçükten büyüge gittiginden yani her parent dal, child dallardan küçük oldugu için dogru heap yapısını temsil eder.
3. dizilimde indis sayısı 5 olan 80 sayısı parent(79) dan küçük oldugu için dizilişi bozar.
bu dizilişleri http://www.bilgisayarkavramlari.com/2008/08/09/dizi-uzerinde-agac-kodlamasi/ dersinden yola çıkarak yaptım. İşlemlerde hata varmıdır hocam.
Yok. Yorumunuz kesinlikle doğru. Bu üç diziden 2. olanı heap yapısına uyar diğerleri uymaz.
hocam elinize sağlık müthiş bir kaynak olmuş. Yalnız tree mantığını düşündüğümüzde, yerleştirmiş olduğunuz ağaçta node3 ve node4 ün yerlerinin değişmesi gerekiyor mu? şimdiden teşekkürler
Tam olarak neredeki node3 ve node4’ü kastediyorsunuz anlamadım ancak yazının içindekileri kastediyorsanız. Yazıda örnek bir yığıt (heap) verilmiştir. Aslında tam olarak diziden heapify edilmiş bir ağaç değil. Tam heapify sonucunda, aşağıdaki şekilde bir ağaç çıkar:
20 / 18 5 / / 12 4 3Yukarıdaki yapıda, ve yazı içerisinde bahsedilen durum, bir şekilde heap oluşturulduktsan sonra sıralama işleminin nasıl yapılacağıdır. Diziden heap oluşturma işlemi sırasında önce veriler ağaca yerleştirilir (Verildiği sıra ile) ardından heapify işlemi yapılır.
Ancak yine de sorunuzu yanlış anlamış olabilirim, daha açık yazarsanız sevinirim.
Heap siralamayi kodlayiniz. Azalan ve Artan olacak ¸sekilde menüye iki
seçenek konsun. Kullanicinin seçimine göre artan veya azalan olarak heap
siralasin. Dizi baslangiçta tanimli olsun. Sonuçta olusan siralama yan yana
yazdirilarak ekran çiktisi kodun sonuna eklensin. acil hemen ilgilenirmisiniz!!! tesekkur ederim simdiden.
Elbette yardımcı olmaya çalışalım. Öncelikle, sitede yayınladığım iki sayfadaki (bu sayfa ve yığıt oluşumunu içeren diğer sayfa http://www.bilgisayarkavramlari.com/2008/08/09/yigin-agaci-heap/ ) kodları birleştirirseniz zaten istediklerinizden birinci kısmını tamamlamış oluyorsunuz. Ardından yığıt oluşumu kodlarından heapify kodunu değiştirerek (büyük küçük dönüşümü) tersten de yığıt (heap) oluşturmuş oluyorsunuz.
Siz kodları birleştirin ve deneyin takıldığınız yer olursa yine yardımcı olmaya çalışırım.
Başarılar
Merhaba hocam, minimum heap yapısında i. en küçük elemanı bulacak şekilde bir algoritma yazsak bu programın kaba kodu nasıl olurdu açıklar mısınız? Teşekkür ederim şimdiden…
Hocam Merge sort karmaşıklığı da n logn , heap sort karmaşıklığı da..Neden merge sort’u veya heap sort’u tercih edelim.Avantajı nedir ?
bahsettiğiniz karmaşıklıklar, en kötü durum analizleridir. Bunlar önemlidir ama bunların dışında da seçimi etkileyen durumlar vardır. Mesela ortalama durum analizi, en iyi durum analizi, hafıza karmaşıklığı, kodlama zorluğu gibi.
Selamlar hocam,
elimde şöyle bir veri dizisi var
müşteri tipi, isim, geliş saati
1,ali,13
2,can,14
1,cem,15
benim heap te görmek istediğim öncelik müşteri tipine gore ve geliş saatine gore heap te minHeap şeklinde tutmak,
nasıl yapabilirim değerli düşüncelerinizi paylaşırmsınız