Yığın nedir (veri yapısı bağlamında)?

Yığın (heap), veri yapısı olarak kullanılan özel bir ağaçtır. Yığının temel özelliği kısmi sıralamadır: herhangi bir düğüm için, ebeveyn düğümünün değeri, çocuk düğümlerinin herhangi birinin değerinden büyük veya eşit olmalıdır (max-heap) veya küçük veya eşit olmalıdır (min-heap).

Ana özellikler:

İkili ağaç: Genellikle ikili ağaç olarak uygulanır, her düğüm en fazla iki çocuğa sahiptir.
Tam ikili ağaç: Tüm seviyelerde, belki de son seviyede, ağaç tamamen doldurulmuştur. Son seviyedeki düğümler soldan sağa doldurulur. Bu, yığının verimli bir şekilde dizi olarak saklanmasını sağlar.
Yığın özelliği:
- Max-heap: Her düğümün değeri, çocuklarının değerlerinden büyük veya eşit olmalıdır. En büyük öğe her zaman köktedir.
- Min-heap: Her düğümün değeri, çocuklarının değerlerinden küçük veya eşit olmalıdır. En küçük öğe her zaman köktedir.

Yığın ile temel işlemler:

Eleman ekleme: Yeni bir eleman ekleme ve yığın özelliğini koruma.
Eleman silme: Kök elemanı (maksimum veya minimum, yığın türüne göre) silme ve yığın özelliğini koruma.
Yığın oluşturma: Bir dizi öğeden yığın oluşturma.

Yığının uygulamaları:

Sıralama: Yığın sıralama algoritması (Heapsort).
Öncelik sıraları: Öğelerin öncelik sırasına göre işlendiği verimli kuyruklar.
Arama algoritmaları: Örneğin, k-inci en büyük öğeyi bulma.
Graf algoritmaları: Örneğin, Dijkstra algoritması.

Yığının dizi ile gösterimi:

Yığın tam ikili ağaç olduğundan, işaretçi kullanmadan verimli bir şekilde dizide saklanabilir.

Bir düğüm i indeksindeyse, sol çocuğu 2*i + 1 indeksindedir.
Sağ çocuğu 2*i + 2 indeksindedir.
Ebeveyn (i - 1) / 2 indeksindedir.

# Min-heap'in dizi olarak gösterimi örneği
heap_array = [10, 15, 20, 17, 25, 30]

# Kök: heap_array[0] = 10
# Kökün sol çocuğu: heap_array[2*0 + 1] = heap_array[1] = 15
# Kökün sağ çocuğu: heap_array[2*0 + 2] = heap_array[2] = 20
# İndeks 3 (17) olan öğenin ebeveyni: heap_array[(3-1)//2] = heap_array[1] = 15