Push ve pop
- Algoritmalar kursu
- Orta seviye
- Ders 43/80
- 4 dk
push ve pop işlemlerinin önceliğe göre çalışmasını öğrenirsin.
Push ve pop
Öncelikli kuyrukta push ve pop, heap'in sift-up ve sift-down işlemlerine dayanır. Push yeni eleman ekler ve yukarı kaydırır.
Pop kökü çıkarır, son elemanı köke taşır ve aşağı kaydırır. Her ikisi O(log n).
Bu işlemler, görev zamanlayıcıda en yüksek öncelikli görevi seçmek için kullanılır.
Uygulamalar
Öncelikli kuyruk birçok yerde kullanılır. Dijkstra'da en kısa mesafedeki düğümü seçmek için. Huffman kodlamada en az sıklıklı karakteri birleştirmek için.
Görev zamanlayıcıda en yüksek öncelikli süreci çalıştırmak için. A* aramada en düşük maliyetli yolu seçmek için.
Heap, bu uygulamaların çekirdeğidir.
Uygulama Pop
pop(arr) yaz. Min-heap'ten kökü çıkar. arr = [1, 3, 2, 5]; print(pop(arr)) ile 1 yazdır.
Başlangıç kodu
def pop(arr):
# Kökü çıkarÖrnek çözüm
def sift_down(arr, n, i):
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)
def pop(arr):
# Kökü çıkar
result = arr[0]
arr[0] = arr[-1]
arr.pop()
if arr:
sift_down(arr, len(arr), 0)
return result
arr = [1, 3, 2, 5]
print(pop(arr))Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Push ve pop: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Push |
Sift-up |
Pop |
Sift-down |
Maliyet |
O(log n) |
Kök |
En küçük |
2 Dijkstra öncelikli kuyruğu ne için kullanır?
- En uzak düğüm
- Rastgele düğüm
- İlk düğüm
- En kısa mesafeli düğüm Doğru cevap
Açıklama: En kısa mesafeli düğüm
3 Pop sonucu
result = arr[____]result = arr[0]Açıklama: 0 doğru.