Özet - Priority queue

Öncelikli kuyruğa iş ekleyip en yüksek öncelikliyi yazdıran mini görev yaparsın.

Özet - Priority queue

Öncelikli kuyruk: en yüksek/düşük öncelikli önce çıkar. Heap ile uygulanır: push O(log n), pop O(log n), peek O(1).

Dijkstra, Huffman, görev zamanlayıcı, A* arama temelidir. Min-heap en küçüğü, max-heap en büyüğü önceliklendirir.

Sıralı diziye göre ekleme çok daha hızlı; sırasız diziye göre çıkarma çok daha hızlı.

Uygulama Özet: push ve pop

push(arr, val) yaz. arr = [2]; push(arr, 1); push(arr, 3); print(arr[0]) ile 1 yazdır.

Örnek çözümü göster

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 = [2]
push(arr, 1)
push(arr, 3)
print(arr[0])

Kendini test et

Özet - Priority queue: kavramları eşleştir

Push

Ekleme
Pop

Çıkarma
Peek

O(1)
Uygulama

Dijkstra

Min-heap kök

Min-heap'te kök = en ____

Cevabı göster

Min-heap'te kök = en küçük

Peek maliyeti nedir?
- O(1)
- O(n)
- O(n log n)
- O(log n)
Cevabı göster

O(1) — O(1)

Sıradaki ders: Proje: Genel bakış

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler