İçeriğe geç

Heap temelleri

Ders 1 / 7 · 5 dk

Heap temelleri

Adım 1/25

Düz bir dizide dört teklif. Ağaç olarak okununca i indeksi, 2i+1 ve 2i+2'nin ebeveyni (parent); ağacın ta kendisi bu aritmetik.

Fikir

Heap, tam bir ikili ağaçtır: her ebeveyn (parent) çocuklarından (child) öndedir; min-heap'te bu, daha küçük olmak demek. Bu, sıralamadan çok daha zayıf bir garanti ve korunması da çok daha ucuz.

Garanti olan yalnız kök. Push ve pop O(log n) sürer; kazanana bakmak (peek) O(1). Ağaç düz bir dizide tutulur: i düğümünün (node) çocukları 2i + 1 ve 2i + 2'dedir.

Gerçek hayattan örnek

Bir müzayede salonunun teklif panosu yalnız o anki en yüksek teklifi gösterir. Kimse bağırılan her teklifin tam sıralamasını tutmaz; bu boşa emek olurdu, çünkü yalnız en üstteki kazanabilir. Yeni bir teklif ya panoya çıkar ya da öbür tekliflerin arasında sessizce kaybolur.

Kod

Sıra sende

Bu kod ne yazdırır?

import heapq
h = [5, 8, 2]
heapq.heapify(h)
heapq.heappush(h, 4)
print(heapq.heappop(h), heapq.heappop(h))

Mini quiz

1 / 3

Bir min-heap'te 0 indeksindeki değer için ne garantidir?