İki heap: anlık medyan
Adım 1/16
Sırt sırta iki heap. low yarısı en büyüğünü tepede tutar; high yarısı en küçüğünü. Orta değer ikisinin arasındadır.
Fikir
Küçük yarıyı bir max-heap'te, büyük yarıyı bir min-heap'te tut. İki kök ortanın iki yanında durur; medyan hep bir bakış uzaklığındadır, yeniden sıralamaya hiç gerek kalmaz.
Her gelen önce low tarafına girer, sonra low'un en büyüğü high'a geçirilir. Tek bir boyut kontrolü iki yarıyı dengede tutar.
Gerçek hayattan örnek
Bir baharat pazarındaki iki kefeli terazi. Her yeni ağırlık sol kefeye konur, oradaki en ağır parça sağa geçirilir ve iki fazla öne geçen kefe birini geri yollar. Terazinin dayanak noktasına en yakın duran şey, ortadaki ağırlıktır.
Kod
Sıra sende
Bu kod ne yazdırır?
import heapq
low, high = [-3, -1], [5, 9] # low is negated: it holds 3 and 1
heapq.heappush(low, -7)
heapq.heappush(high, -heapq.heappop(low))
print(-low[0], high[0])Mini quiz
1 / 3