Ekleme

Yeni elemanı sona koyup yukarı kaydırarak eklemeyi öğrenirsin.

Ekleme

Heap'e eleman eklerken önce sona eklenir, sonra yukarı kaydırma (sift-up) yapılır: ebeveyninden küçükse (min-heap) takas edilir, köke kadar devam eder.

Her adımda bir düzey yukarı çıkılır; toplam O(log n). Ekleme sonrası heap özelliği korunur.

Sift-up, yeni elemanın doğru yerini bulana kadar devam eder; en kötü durumda köke kadar gider.

Sift-up adımları

Sift-up: i yeni elemanın indeksi. parent = (i-1)//2. Eğer arr[i] < arr[parent] ise takas et, i = parent, tekrar et.

i == 0 (kök) olana veya ebeveyninden büyük/eşit olana kadar devam eder. Bu, min-heap özelliğini geri kazandırır.

Her takas bir düzey yukarı çıkar; en fazla log n takas yapılır.

Uygulama Sift-up (ekleme)

sift_up(arr, i) yaz. Min-heap için yukarı kaydır. arr = [1, 3, 2, 0]; sift_up(arr, 3); print(arr) ile [0, 1, 2, 3] yazdır.

Örnek çözümü göster

def sift_up(arr, i):
    # Yukarı kaydır
    while i > 0:
        parent = (i - 1) // 2
        if arr[i] < arr[parent]:
            arr[i], arr[parent] = arr[parent], arr[i]
            i = parent
        else:
            break
arr = [1, 3, 2, 0]
sift_up(arr, 3)
print(arr)

Kendini test et

Sift-up karşılaştırma

while i > 0 and arr[i] ____arr[parent]:

Cevabı göster

while i > 0 and arr[i] <arr[parent]:

Ekleme: kavramları eşleştir

Sift-up

Yukarı kaydır
Ebeveyn

(i-1)//2
Takas

Yer değiştir
Maliyet

O(log n)
Sift-up ne zaman durur?
- Her zaman kökte
- Sadece yaprakta
- Kökte veya ebeveynden büyükse
- Asla
Cevabı göster

Kökte veya ebeveynden büyükse — Kökte veya ebeveynden büyükse

Sıradaki ders: Çıkarma

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler