Yığın nedir?

Yığın (heap), özel bir ağaç yapısıdır ve yığın özelliğini sağlar. Bu özellik, herhangi bir kök dışındaki her düğüm için, bu düğümün anahtar değerinin, ebeveyninin anahtar değeriyle belirli bir ilişkide olması gerektiğini belirtir. İki ana yığın türü vardır:

• Max-yığın (Max-heap): Her düğümün anahtar değeri, çocuklarının anahtar değerlerinden küçük değildir. En büyük öğe köktedir.
• Min-yığın (Min-heap): Her düğümün anahtar değeri, çocuklarının anahtar değerlerinden büyük değildir. En küçük öğe köktedir.

Yığın genellikle bir dizi olarak uygulanır, bu da öğelere etkin erişim ve işlemlerin gerçekleştirilmesini sağlar. Dizide ebeveyn ve çocuklar arasındaki ilişki şöyledir:

• i indeksine sahip bir öğe için (sıfırdan başlar), sol çocuğu 2i + 1 indeksindedir.
• Sağ çocuğu 2i + 2 indeksindedir.
• Ebeveyni floor((i - 1) / 2) indeksindedir.

Yığın üzerindeki temel işlemler:

• Ekleme (Insert): Yeni bir öğe ekleme. Çalışma süresi O(log n), burada n öğe sayısıdır.
• Extract-Max / Extract-Min: En büyük (max-yığında) veya en küçük (min-yığında) öğeyi silip geri döndürme. Çalışma süresi O(log n).
• Heapify (Yığın oluşturma): Rastgele bir diziyi yığına dönüştürme. Çalışma süresi O(n).

Yığınlar, sıralama algoritmalarında (örneğin, yığın sıralaması), öncelikli kuyruklarda ve en kısa yol algoritmalarında (örneğin, Dijkstra algoritması) kullanılır.