Özet - Priority queue
- Algoritmalar kursu
- Orta seviye
- Ders 44/80
- 4 dk
Ö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.
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 = [2]
push(arr, 1)
push(arr, 3)
print(arr[0])Beklenen çıktı
1
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Priority queue: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Push |
Ekleme |
Pop |
Çıkarma |
Peek |
O(1) |
Uygulama |
Dijkstra |
2 Min-heap kök
Soru
Min-heap'te kök = en ____
Cevap
Min-heap'te kök = en küçükAçıklama: küçük doğru.
3 Peek maliyeti nedir?
- O(1) Doğru cevap
- O(n)
- O(n log n)
- O(log n)
Açıklama: O(1)