Aula por Lúcio Cardoso
A estrutura de dados Min Queue é uma adaptação da queue do C++. Nela, podemos realizar as seguintes operações:
- Adicionar um elemento de valor $$v$$ atrás da fila
- Remover o elemento da frente da fila
- Responder qual o elemento de menor valor presente na fila
Descrição da Estrutura
Para armazenar as informações da estrutura, utilizaremos um deque. O deque é uma estrutura semelhante à queue, com a diferença de que podemos inserir/remover elementos dos dois lados da fila.
Em particular, cada posição do deque guardará um par de valores: O valor do elemento e o tempo em que foi adicionado (o primeiro elemento adicionado foi adicionado no tempo 1, e assim sucessivamente).
Função $$push(v)$$
A função $$push(v)$$ insere um elemento de valor $$v$$ na parte de trás da fila.
Seja $$v_0$$ o elemento atual no fundo da fila. Se $$v_0 \geq v$$, do momento em que $$v$$ foi adicionado em diante, $$v_0$$ nunca será o valor mínimo na estrutura, pois $$v$$ é menor e, por estar atrás de $$v_0$$, será removido em algum tempo depois de $$v_0$$. Logo, antes de adicionar $$v$$, iremos remover todos os elementos $$v_0$$ do fundo da fila enquanto $$v_0 \geq v$$. Após isso, vamos inserir o par $$(v, tempo)$$ no fundo do deque.
Perceba que, dessa forma, a Min Queue estará sempre ordenada de maneira crescente, e, por tanto, o menor elemento na estrutura será sempre o elemento na frente da fila. Agora, como removemos elementos da estrutura, precisamos de um cuidado adicional na função $$pop()$$.
Função $$pop()$$
A função $$pop()$$ remove o elemento presente na frente da fila.
Perceba que, na função $$push()$$, removemos elementos do fundo da fila, e portanto, é possível que o elemento que deveria estar na frente da fila ao executarmos o comando $$pop()$$ já tenha sido removido.
Para conferir isto, iremos guardar duas variáveis fora da estrutura: $$l$$ e $$r$$. Estas variáveis indicam, respectivamente, o tempo em que o elemento na frente da fila foi inserido (mesmo se este já foi removido) e o tempo em que será adicionado o próximo elemento no fundo na fila. Assim, é muito simples remover um elemento: Basta checar se o tempo do elemento na frente do deque é igual a $$l$$. Se sim, removemos ele, senão, o elemento da frente já foi removido antes e não fazemos nada.
Para atualizar as variáveis $$l$$ e $$r$$, basta somar um no valor de $$r$$ cada vez que adicionarmos um elemento com a função $$push()$$ e somar um em $$l$$ a cada vez que removemos um elemento da frente da fila.
Função $$getmin()$$
A função $$getmin()$$ retorna o elemento de menor valor presente na fila.
Como já dito anteriormente, a estrutura foi mantida de tal forma que o elemento mínimo será aquele na frente da fila. Logo, para retornar o menor elemento, basta retornamos o valor do elemento na frente do deque.
Complexidade
Inicialmente, sabemos que as funções $$getmin()$$ e $$pop()$$ possuem complexidade $$O(1)$$. Além disso, cada elemento da estrutura foi removido/adicionado no máximo uma vez. Logo, a complexidade final após todas as operações terem sido realizadas será $$O(n)$$, onde $$n$$ é o tamanho da fila. Assim, dizemos que cada operação $$push()$$ terá complexidade amortizada $$O(1)$$.
Confira o código final da Min Queue, para melhor entendimento:
https://gist.github.com/luciocf/7b9e6f0680bbfd5ef65bc84216bd89d9