Özet - Heap

Max-heap'e eleman ekleyip kökü yazdıran mini görev yaparsın.

Özet - Heap

Heap: tam ikili ağaç, dizi temsili. Min-heap'te kök en küçük. Ekleme O(log n) (sift-up), çıkarma O(log n) (sift-down).

Ebeveyn (i-1)//2, çocuklar 2i+1, 2i+2. Heap sort ve öncelikli kuyruğun temeli.

Build heap O(n); tüm yaprak olmayanlar heapify edilir.

Uygulama Özet: heap ekleme

heap_insert(arr, val) yaz. Sona ekle, sift_up. arr = [1, 3]; heap_insert(arr, 0); print(arr) ile [0, 3, 1] 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 heap_insert(arr, val):
    # Heap'e ekle
    arr.append(val)
    sift_up(arr, len(arr) - 1)
arr = [1, 3]
heap_insert(arr, 0)
print(arr)

Kendini test et

Özet - Heap: kavramları eşleştir

Min-heap

Kök en küçük
Sift-up

Ekleme
Sift-down

Çıkarma
Build heap

O(n)

Ebeveyn

parent = (i - 1) // ____

Cevabı göster

parent = (i - 1) // 2

Heap build maliyeti nedir?
- O(n)
- O(log n)
- O(n log n)
- O(1)
Cevabı göster

O(n) — O(n)

Sıradaki ders: Öncelikli kuyruk nedir?

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler