Min ve max heap
- Algoritmalar kursu
- Orta seviye
- Ders 37/80
- 4 dk
Min-heap ve max-heap arasındaki farkı öğrenirsin.
Min ve max heap
Min-heap'te her düğüm çocuklarından küçük veya eşittir; kök en küçüktür. Max-heap'te her düğüm çocuklarından büyük veya eşittir; kök en büyüktür.
Heap, tam ikili ağaç olarak dizi ile tutulur. Ebeveyn (i-1)//2, sol çocuk 2i+1, sağ çocuk 2i+2.
Min-heap, öncelikli kuyrukta en küçük elemanı hızlı almak için kullanılır; max-heap ise en büyük için.
Ebeveyn-çocuk
Dizi temsilinde i indeksli düğümün ebeveyni (i-1)//2, sol çocuğu 2i+1, sağ çocuğu 2i+2.
Kök arr[0]'dır ve ebeveyni yoktur. Yapraklar dizinin ikinci yarısında bulunur (i ≥ n//2).
Bu formüller O(1)'de ebeveyn-çocuk ilişkisi verir; işaretçi gerekmez.
Uygulama Min-heap kontrolü
is_min_heap(arr) yaz. Her çocuğun ebeveynden büyük veya eşit. print(is_min_heap([1, 3, 2, 5, 4])) ile True yazdır.
Başlangıç kodu
def is_min_heap(arr):
# Min-heap kontrolüÖrnek çözüm
def is_min_heap(arr):
# Min-heap kontrolü
for i in range(1, len(arr)):
if arr[(i - 1) // 2] > arr[i]:
return False
return True
print(is_min_heap([1, 3, 2, 5, 4]))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Min-heap'te kök nedir?
- En büyük
- En küçük eleman Doğru cevap
- Ortanca
- Rastgele
Açıklama: En küçük eleman
2 Ebeveyn
parent = (i - 1) // ____parent = (i - 1) // 2Açıklama: 2 doğru.
3 Min ve max heap: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Min-heap |
Kök en küçük |
Max-heap |
Kök en büyük |
Ebeveyn |
(i-1)//2 |
Sol çocuk |
2i+1 |