Ekleme
- Algoritmalar kursu
- Orta seviye
- Ders 38/80
- 4 dk
Yeni elemanı sona koyup yukarı kaydırarak eklemeyi öğrenirsin.
Ekleme
Heap'e eleman eklerken önce sona eklenir, sonra yukarı kaydırma (sift-up) yapılır: ebeveyninden küçükse (min-heap) takas edilir, köke kadar devam eder.
Her adımda bir düzey yukarı çıkılır; toplam O(log n). Ekleme sonrası heap özelliği korunur.
Sift-up, yeni elemanın doğru yerini bulana kadar devam eder; en kötü durumda köke kadar gider.
Sift-up adımları
Sift-up: i yeni elemanın indeksi. parent = (i-1)//2. Eğer arr[i] < arr[parent] ise takas et, i = parent, tekrar et.
i == 0 (kök) olana veya ebeveyninden büyük/eşit olana kadar devam eder. Bu, min-heap özelliğini geri kazandırır.
Her takas bir düzey yukarı çıkar; en fazla log n takas yapılır.
Uygulama Sift-up (ekleme)
sift_up(arr, i) yaz. Min-heap için yukarı kaydır. arr = [1, 3, 2, 0]; sift_up(arr, 3); print(arr) ile [0, 1, 2, 3] yazdır.
Başlangıç kodu
def sift_up(arr, i):
# Yukarı kaydırÖrnek çözüm
def sift_up(arr, i):
# Yukarı kaydır
while i > 0:
parent = (i - 1) // 2
if arr[i] < arr[parent]:
arr[i], arr[parent] = arr[parent], arr[i]
i = parent
else:
break
arr = [1, 3, 2, 0]
sift_up(arr, 3)
print(arr)Beklenen çıktı
[0, 1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Sift-up karşılaştırma
while i > 0 and arr[i] ____arr[parent]:while i > 0 and arr[i] <arr[parent]:Açıklama: < doğru.
2 Ekleme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Sift-up |
Yukarı kaydır |
Ebeveyn |
(i-1)//2 |
Takas |
Yer değiştir |
Maliyet |
O(log n) |
3 Sift-up ne zaman durur?
- Her zaman kökte
- Sadece yaprakta
- Kökte veya ebeveynden büyükse Doğru cevap
- Asla
Açıklama: Kökte veya ebeveynden büyükse