Heap nedir?
- Algoritmalar kursu
- Orta seviye
- Ders 9/80
- 4 dk
Tam ikili ağaç şeklinde yığın (heap) veri yapısını öğrenirsin.
Heap nedir?
Heap, tam ikili ağaç (complete binary tree) olarak tutulan ve heap özelliği taşıyan bir veri yapısıdır. Max-heap'te her düğüm, çocuklarından büyük veya eşittir; min-heap'te küçük veya eşittir.
Dizi olarak tutulur: kök arr[0], bir düğümün çocukları 2i+1 ve 2i+2, ebeveyni (i-1)//2.
Heap sort, önce diziyi max-heap yapar, sonra kökü sona taşıyıp heap'i yeniden kurar. Bu işlem sıralama verir.
Dizi temsili
Heap, tam ikili ağaç olduğu için boşluk olmadan diziye yerleştirilebilir. Düzey düzey, soldan sağa.
İndeks i için: sol çocuk 2i+1, sağ çocuk 2i+2, ebeveyn (i-1)//2. Bu formüller ebeveyn-çocuk ilişkilerini O(1)'de verir.
İşaretçi kullanılmaz; bu yüzden heap, Bellek açısından verimlidir.
Uygulama Heap özelliği kontrolü
is_max_heap(arr) yaz. Dizinin max-heap olup olmadığını kontrol et. print(is_max_heap([9, 5, 8, 1, 3])) ile True yazdır.
Başlangıç kodu
def is_max_heap(arr):
# Max-heap kontrolüÖrnek çözüm
def is_max_heap(arr):
# Max-heap kontrolü
for i in range(1, len(arr)):
if arr[(i - 1) // 2] < arr[i]:
return False
return True
print(is_max_heap([9, 5, 8, 1, 3]))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Max-heap'te kök hangisidir?
- En küçük
- En büyük eleman Doğru cevap
- Ortanca
- Rastgele
Açıklama: En büyük eleman
2 Sol çocuk
sol = 2 * i + ____sol = 2 * i + 1Açıklama: 1 doğru.
3 Heap nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Max-heap |
Kök en büyük |
Min-heap |
Kök en küçük |
Sol çocuk |
2i+1 |
Ebeveyn |
(i-1)//2 |