Pular para o conteúdo

Dois heaps: mediana contínua

Aula 1 de 4 · 6 min

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

Qual heap guarda a metade de baixo?