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