What is a Heap?

Bir yığın (heap), basit bir değişmezi takip eden ağaç şeklinde bir veri yapısıdır: her ebeveyn, çocuklarından daha küçüktür (veya onlara eşittir). En küçük değer her zaman kökte bulunur ve O(1) sürede okunmaya hazırdır. Bu özel türe min-yığın (min-heap) denir; kökte en büyük değerin bulunduğu tam tersi durum ise maks-yığın (max-heap) olarak adlandırılır.

İşin zekice kısmı depolamadır. Onu bir ağaç olarak düşünsek de, bir yığın düz bir dizi (array) içinde yaşar. i indeksindeki düğüm için:

• Ebeveyni (i - 1) / 2 indeksindedir.
• Sol çocuğu 2 * i + 1 indeksindedir.
• Sağ çocuğu 2 * i + 2 indeksindedir.

İşaretçi yok, düğüm nesnesi yok: sadece indeks matematiği. Bu, yığınları önbellek dostu ve uygulanması kolay hale getirir.

Bir min-yığın üzerindeki beş ana işlem şunlardır:

1. Peek: En küçük değeri (kökü) döndürür.
2. Insert: Bir değer ekler ve onu yerine ulaşana kadar yukarı kaydırır (bubble up).
3. ExtractMin: En küçük değeri kaldırır ve döndürür.
4. Size: Kaç değerin saklandığını döndürür.
5. IsEmpty: Yığının boş olup olmadığını kontrol eder.

Hadi bir MinHeap sınıfı oluşturalım!