projetar uma fila que suporte a função getMedian - algoritmo, estruturas de dados

Esta é uma questão de entrevista. Você precisa criar uma fila que armazena valores inteiros e tem uma função getMedian () que retorna o elemento mediano da fila atual. Você pode usar O (n) espaço extra.

O getMedian () pode ser implementado com complexidade de tempo <O (n)?

Por exemplo: Quando a fila possui os seguintes valores (2, 1, 2, 2, 6, 4, 2, 5) este método retorna 2 e não remove esse objeto.

Respostas:

A implementação conhecida para o seu problema é assim:

O que você precisa implementar é 2 heaps, um será um min-heap e o outro um max-heap.
Além disso, você precisará de um número inteiro para nos informar o número de objetos na sua fila.

As restrições para os heaps são as seguintes:
1. O min-heap terá os objetos maiores da sua fila
2. O heap máximo terá os objetos menores da sua fila
3. O heap máximo terá o mesmo ou mais 1 objeto que seu heap mínimo

Dessa forma, se você tiver um número ímpar de objetosa mediana seria exatamente o objeto max no seu heap máximo. Se você tiver um número par de objetos, sua mediana seria a média de ambas as raízes de seus heaps (máximo de heap máximo, min de heap mínimo).

É importante notar que, se os seus montestornar-se desigual, por exemplo, se você vai "pop" de um determinado heap, você precisará remover do outro heap e movê-lo. Mas isso não é um problema, pois tudo que você precisa para lidar com as raízes de seus montes e nada mais.

A complexidade do tempo de getMedian se torna O (1)

Acabei de encontrar um artigo sobre o assunto: ligação

Responda para comentar

O heap máximo mantém a metade menor elementos.
Quando você adiciona um novo número à fila, primeiro verifica qual é o número de objetos na fila.
se o número que você está adicionando for um número par, isso significa que ele precisa ser adicionado ao heap máximo, pois as duas filas são iguais em tamanho.
Você então vê qual é o máximo no heap máximo.
Se for maior que seu número, você pode simplesmente inseri-lo no heap máximo.
se for menor, o que significa que seu novo número pode ser maior que um número no min-heap.
então você vê o que o min no min-heap é.
se o seu número for menor que o min, então você pode inseri-lo no heap máximo, se ele for maior, então mova o min no min-heap para o heap máximo e insira seu novo número no min-heap. heap.
Se o número for um número ímpar, você precisará adicionar ao min-heap, pois o heap máximo tem mais um, e assim por diante.

É um pouco complicado, mas se você ainda não entender eu não me importo de codificá-lo para você