Özet - Heap
- Algoritmalar kursu
- Orta seviye
- Ders 40/80
- 4 dk
Max-heap'e eleman ekleyip kökü yazdıran mini görev yaparsın.
Özet - Heap
Heap: tam ikili ağaç, dizi temsili. Min-heap'te kök en küçük. Ekleme O(log n) (sift-up), çıkarma O(log n) (sift-down).
Ebeveyn (i-1)//2, çocuklar 2i+1, 2i+2. Heap sort ve öncelikli kuyruğun temeli.
Build heap O(n); tüm yaprak olmayanlar heapify edilir.
Uygulama Özet: heap ekleme
heap_insert(arr, val) yaz. Sona ekle, sift_up. arr = [1, 3]; heap_insert(arr, 0); print(arr) ile [0, 3, 1] yazdır.
Başlangıç kodu
def heap_insert(arr, val):
# 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 heap_insert(arr, val):
# Heap'e ekle
arr.append(val)
sift_up(arr, len(arr) - 1)
arr = [1, 3]
heap_insert(arr, 0)
print(arr)Beklenen çıktı
[0, 3, 1]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - Heap: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Min-heap |
Kök en küçük |
Sift-up |
Ekleme |
Sift-down |
Çıkarma |
Build heap |
O(n) |
2 Ebeveyn
Soru
parent = (i - 1) // ____
Cevap
parent = (i - 1) // 2Açıklama: 2 doğru.
3 Heap build maliyeti nedir?
- O(n) Doğru cevap
- O(log n)
- O(n log n)
- O(1)
Açıklama: O(n)