Push ve pop

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.

Örnek çözümü göster

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))

Kendini test et

Push ve pop: kavramları eşleştir

Push

Sift-up
Pop

Sift-down
Maliyet

O(log n)
Kök

En küçük
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
Cevabı göster

En kısa mesafeli düğüm — En kısa mesafeli düğüm
Pop sonucu
```
result = arr[____]
```
Cevabı göster
```
result = arr[0]
```

Sıradaki ders: Özet - Priority queue

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler