Heap ile uygulama
- Algoritmalar kursu
- Orta seviye
- Ders 42/80
- 4 dk
Öncelikli kuyruğu heap ile uygulamanın O(log n) verdiğini öğrenirsin.
Push ve pop
Push: elemanı sona ekle, sift-up yap. O(log n).
Pop: kökü kaydet, son elemanı köke taşı, sift-down yap, eski kökü döndür. O(log n).
Bu iki işlem, öncelikli kuyruğun temel arayüzüdür. Heap sayesinde her ikisi de verimlidir ve dengelidir.
Pop detayı
Pop: önce result = arr[0] kaydet. Sonra arr[0] = arr[-1], arr.pop() (son elemanı kaldır). Sonra sift_down(arr, n, 0).
Eğer heap tek elemanlıysa direkt arr.pop() yeterli. Boş heap'te pop hata verir.
Pop sonrası heap özelliği korunur; bir sonraki en küçük köke çıkar.
Uygulama Push
push(arr, val) yaz. Min-heap'e ekle. arr = [1, 3, 2]; push(arr, 0); print(arr) ile [0, 1, 2, 3] yazdır.
Başlangıç kodu
def push(arr, val):
# Min-heap'e ekleÖrnek çözüm
def sift_up(arr, i):
while i > 0:
parent = (i - 1) // 2
if arr[i] < arr[parent]:
arr[i], arr[parent] = arr[parent], arr[i]
i = parent
else:
break
def push(arr, val):
# Min-heap'e ekle
arr.append(val)
sift_up(arr, len(arr) - 1)
arr = [1, 3, 2]
push(arr, 0)
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 Push işlemi
arr.append(val)
sift_up(arr, len(arr) - ____)arr.append(val)
sift_up(arr, len(arr) - 1)Açıklama: 1 doğru.
2 Heap ile uygulama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Push |
Sona ekle + sift-up |
Pop |
Kök al + sift-down |
Peek |
Kök oku |
Boş |
Hata |
3 Pop sonrası ne yapılır?
- Sift-up
- Hiçbir şey
- Sift-down Doğru cevap
- Yeniden build
Açıklama: Sift-down