Çıkarma

Kökü çıkarıp son elemanla değiştirip aşağı kaydırmayı öğrenirsin.

Çıkarma

Heap'ten kök (en küçük) çıkarılırken: son eleman köke taşınır, heap boyutu bir azalır, sonra aşağı kaydırma (sift-down) yapılır.

Sift-down: kök, çocuklarından küçükse durur; değilse küçük çocukla takas edilir ve aşağı inilir. Yaprakta durur.

Çıkarma O(log n): kök değişimi O(1) + sift-down O(log n).

Sift-down detay

Sift-down: i kök indeksi. Sol ve sağ çocuk hesaplanır. Küçük çocuk bulunur. Eğer arr[i] küçük çocuktan büyükse takas, i = küçük çocuk indeksi, tekrar et.

Yaprak olunca (çocuk yok) veya çocuklardan küçük/eşit olunca durur. Min-heap özelliği geri kazanılır.

Her takas bir düzey aşağı; en fazla log n takas.

Uygulama Sift-down (çıkarma)

sift_down(arr, n, i) yaz. Min-heap için aşağı kaydır. arr = [3, 1, 2]; sift_down(arr, 3, 0); print(arr) ile [1, 3, 2] yazdır.

Örnek çözümü göster

def sift_down(arr, n, i):
    # Aşağı kaydır
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        sift_down(arr, n, smallest)
arr = [3, 1, 2]
sift_down(arr, 3, 0)
print(arr)

Kendini test et

Çıkarma: kavramları eşleştir

Çıkarma

Kökü al
Sift-down

Aşağı kaydır
Küçük çocuk

Takas
Maliyet

O(log n)
Sift-down hangi çocukla takas yapar?
- Büyük olan
- Sağ her zaman
- Sol her zaman
- Küçük olan
Cevabı göster

Küçük olan — Küçük olan

Sift-down koşulu

if arr[smallest] ____arr[i]:

Cevabı göster

if arr[smallest] <arr[i]:

Sıradaki ders: Özet - Heap

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler