Heap ile uygulama

Öncelikli kuyruğu heap ile uygulamanın O(log n) verdiğini öğrenirsin.

Push ve pop

Push: elemanı sona ekle, sift-up yap. O(log n).

Pop: kökü kaydet, son elemanı köke taşı, sift-down yap, eski kökü döndür. O(log n).

Bu iki işlem, öncelikli kuyruğun temel arayüzüdür. Heap sayesinde her ikisi de verimlidir ve dengelidir.

Pop detayı

Pop: önce result = arr[0] kaydet. Sonra arr[0] = arr[-1], arr.pop() (son elemanı kaldır). Sonra sift_down(arr, n, 0).

Eğer heap tek elemanlıysa direkt arr.pop() yeterli. Boş heap'te pop hata verir.

Pop sonrası heap özelliği korunur; bir sonraki en küçük köke çıkar.

Uygulama Push

push(arr, val) yaz. Min-heap'e ekle. arr = [1, 3, 2]; push(arr, 0); print(arr) ile [0, 1, 2, 3] yazdır.

Örnek çözümü göster

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 push(arr, val):
    # Min-heap'e ekle
    arr.append(val)
    sift_up(arr, len(arr) - 1)
arr = [1, 3, 2]
push(arr, 0)
print(arr)

Kendini test et

Push işlemi

arr.append(val)
sift_up(arr, len(arr) - ____)

Cevabı göster

arr.append(val)
sift_up(arr, len(arr) - 1)

Heap ile uygulama: kavramları eşleştir

Push

Sona ekle + sift-up
Pop

Kök al + sift-down
Peek

Kök oku
Boş

Hata
Pop sonrası ne yapılır?
- Sift-up
- Hiçbir şey
- Sift-down
- Yeniden build
Cevabı göster

Sift-down — Sift-down

Sıradaki ders: Push ve pop

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler