Çıkarma
- Algoritmalar kursu
- Orta seviye
- Ders 39/80
- 4 dk
Kökü çıkarıp son elemanla değiştirip aşağı kaydırmayı öğrenirsin.
Çıkarma
Heap'ten kök (en küçük) çıkarılırken: son eleman köke taşınır, heap boyutu bir azalır, sonra aşağı kaydırma (sift-down) yapılır.
Sift-down: kök, çocuklarından küçükse durur; değilse küçük çocukla takas edilir ve aşağı inilir. Yaprakta durur.
Çıkarma O(log n): kök değişimi O(1) + sift-down O(log n).
Sift-down detay
Sift-down: i kök indeksi. Sol ve sağ çocuk hesaplanır. Küçük çocuk bulunur. Eğer arr[i] küçük çocuktan büyükse takas, i = küçük çocuk indeksi, tekrar et.
Yaprak olunca (çocuk yok) veya çocuklardan küçük/eşit olunca durur. Min-heap özelliği geri kazanılır.
Her takas bir düzey aşağı; en fazla log n takas.
Uygulama Sift-down (çıkarma)
sift_down(arr, n, i) yaz. Min-heap için aşağı kaydır. arr = [3, 1, 2]; sift_down(arr, 3, 0); print(arr) ile [1, 3, 2] yazdır.
Başlangıç kodu
def sift_down(arr, n, i):
# Aşağı kaydırÖrnek çözüm
def sift_down(arr, n, i):
# Aşağı kaydır
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] < arr[smallest]:
smallest = left
if right < n and arr[right] < arr[smallest]:
smallest = right
if smallest != i:
arr[i], arr[smallest] = arr[smallest], arr[i]
sift_down(arr, n, smallest)
arr = [3, 1, 2]
sift_down(arr, 3, 0)
print(arr)Beklenen çıktı
[1, 3, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Çıkarma: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Çıkarma |
Kökü al |
Sift-down |
Aşağı kaydır |
Küçük çocuk |
Takas |
Maliyet |
O(log n) |
2 Sift-down hangi çocukla takas yapar?
- Büyük olan
- Sağ her zaman
- Sol her zaman
- Küçük olan Doğru cevap
Açıklama: Küçük olan
3 Sift-down koşulu
if arr[smallest] ____arr[i]:if arr[smallest] <arr[i]:Açıklama: < doğru.