Min ve max heap

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.

Örnek çözümü göster

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

Kendini test et

Min-heap'te kök nedir?
- En büyük
- En küçük eleman
- Ortanca
- Rastgele
Cevabı göster

En küçük eleman — En küçük eleman

Ebeveyn

parent = (i - 1) // ____

Cevabı göster

parent = (i - 1) // 2

Min ve max heap: kavramları eşleştir

Min-heap

Kök en küçük
Max-heap

Kök en büyük
Ebeveyn

(i-1)//2
Sol çocuk

2i+1

Sıradaki ders: Ekleme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler