Estruturas de Dados 1 - Min/Max Queue

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: