Dois heaps: mediana contínua
Passo 1 de 16
Dois heaps, costas com costas. A metade low guarda o maior no topo; a metade high, o menor. O meio fica entre eles.
A ideia
Guarde a metade menor em um max-heap e a maior em um min-heap. As duas raízes ficam uma de cada lado do meio, então a mediana está sempre a um olhar de distância — nunca é preciso reordenar.
Toda chegada entra no lado de baixo (low), e depois o maior de low passa para o lado de cima (high). Uma checagem de tamanho mantém as metades equilibradas.
Exemplo do mundo real
A balança de dois pratos de um mercado de especiarias. Cada peso novo cai no prato esquerdo, o item mais pesado dali passa para o direito, e um prato que fica dois à frente devolve um. O que estiver mais perto do ponto de apoio é o peso do meio.
O código
Sua vez
O que isto imprime?
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