Karşılaştırma
Takas
Çıkarılan

  • Aşağı inen
  • Karşılaştırılan
  • Takas edilen
  • Yerinde

Yığın sıralaması hakkında daha fazla

Yığın sıralaması

Yığın sıralaması (heapsort) listeyi ikili ağaç olarak okur ve her ebeveynin çocuklarından küçük olmadığı bir maksimum yığına dönüştürür. En büyük değer böylece tepeye gelir. Onu sona taşıyın, orada kalsın; yığını onarın ve tekrarlayın. Uygulama yığını çubukların üstünde bir ağaç olarak çizer, böylece her değerin aşağı inişini takip edebilirsiniz. Sıralamayı izlemek için Oynat'a, her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'ye basın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Çubukların üstündeki ağaç, aynı değerleri yığın olarak gösterir. Kutucuklar karşılaştırmaları, takasları ve yığından çıkarılan değerleri sayar. Çubuk sayısını ve başlangıç düzenini seçin ya da kendi sayılarınızı yazın. Tahta seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Çubuk sayısını ve başlangıç düzenini seçin: rastgele, neredeyse sıralı, ters veya az sayıda farklı değerle. Ya da kendi sayılarınızı yazın.
  2. Oynat'a basın ya da her seferinde bir karşılaştırma ilerlemek için Adım ve Geri'yi kullanın. Sıralamanın herhangi bir yerine atlamak için adım kaydırıcısını sürükleyin.
  3. Ağacı izleyin: önce yığın kurulana kadar her ebeveyn aşağı iner, sonra kök sona taşınır ve yığın bir küçülür.

Yığın sıralaması nasıl çalışır

Listeyi bir ağaç olarak okuyun: i konumundaki değerin çocukları 2i + 1 ve 2i + 2 konumlarındadır. Son ebeveynden başlayarak her ebeveyni aşağı indirip bir maksimum yığın kurun: bir değer çocuklarının büyüğünden küçük olduğu sürece ikisi yer değiştirir. Kök en büyük değeri tuttuğunda, onu yığının son değeriyle takas edin. O değer artık kesinleşmiştir, yığın bir kısalır ve yeni kök, yığını yeniden kurmak için aşağı iner. Yığın boşalana kadar tekrarlayın.

Her zaman n log n, yerinde

Ağacın yaklaşık log₂ n seviyesi vardır; bu yüzden her aşağı indirme en fazla yaklaşık 2 log₂ n karşılaştırma yapar, yığını kurmak ise 2n'den az karşılaştırma ister. Bu da yığın sıralamasına en kötü durumda yaklaşık 2n log₂ n karşılaştırma verir, hem de ek tampon olmadan: 40 değer için en fazla 352. Hızlı sıralamanın aksine kötü girdisi yoktur, birleştirmeli sıralamanın aksine ek bellek gerektirmez. Pratikte genellikle ikisinden de yavaştır, çünkü liste içinde sıçrar; ayrıca kararlı değildir.

Sık sorulan sorular

Yığın sıralaması nasıl çalışır?

Listeyi bir maksimum yığına, yani listede saklanan ve her ebeveynin çocuklarından küçük olmadığı bir ağaca dönüştürür. Sonra kökteki en büyük değeri tekrar tekrar yığının sonuna taşır ve yığını onarmak için yeni kökü aşağı indirir.

Yığın nedir?

İşaretçi kullanmadan bir listede saklanan tam bir ikili ağaç: i konumunun çocukları 2i + 1 ve 2i + 2 konumlarıdır. Maksimum yığında her ebeveyn çocuklarından küçük değildir, bu yüzden en büyük değer her zaman kökte, yani 0 konumundadır.

Yığını kurmak neden hızlıdır?

Değerlerin çoğu ağacın alt kısmındadır ve yalnızca bir iki seviye aşağı inebilir. Tüm seviyelerdeki iş toplandığında kurulumun tamamı n log n değil, 2n'den az karşılaştırma tutar.

Yığın sıralaması kararlı mıdır?

Hayır. Kökü sona taşımak değerleri uzak mesafelere taşır, bu yüzden eşit değerlerin sırası değişebilir.

Sayılarım bir yere gönderiliyor mu?

Hayır. Sıralama tarayıcınızda çalışır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git