Fila de prioridade: quando furar a fila é justo

Quando a ordem de chegada não basta

A fila comum é justa quando todos são iguais, mas há situações em que tratar todos igual seria injusto. O melhor exemplo é o pronto-socorro. Se o hospital atendesse estritamente por ordem de chegada, alguém com um problema grave poderia esperar atrás de dez casos leves e correr risco. Por isso o pronto-socorro usa triagem: um caso mais urgente é atendido antes, mesmo tendo chegado depois. Essa lógica é a fila de prioridade. Ela continua sendo uma fila, com espera e atendimento, mas a ordem de saída não é mais só a de chegada: cada elemento carrega uma prioridade, e o de maior prioridade é o próximo a sair.

Repare que a prioridade não é uma quebra de regra, é uma regra diferente e explícita. Na fila comum, a única informação que importa é quando você chegou. Na fila de prioridade, cada elemento traz dois dados: a informação em si e a sua importância. O programa, na hora de escolher quem sai, compara as importâncias e escolhe a maior. E quando duas importâncias empatam, aí sim a fila volta a usar a ordem de chegada como critério de desempate, para que quem esperou mais entre dois casos igualmente urgentes seja atendido primeiro. É a combinação das duas regras que torna a estrutura tão útil.

A ordem de saída segue a prioridade

Para prever quem sai de uma fila de prioridade, esqueça por um momento a ordem de chegada e olhe primeiro para as prioridades. O de maior importância vai na frente, seja qual for a hora em que entrou. Depois que ele sai, a próxima saída é o de maior importância entre os que restaram, e assim por diante. Só quando duas importâncias forem iguais é que você recorre à ordem de chegada para desempatar. É um raciocínio em duas camadas: primeiro compara a urgência; se empatar, compara a chegada. Treinar essa ordem de decisão é o que impede o erro de tratar a fila de prioridade como se fosse uma fila comum.

Onde a fila de prioridade trabalha

A fila de prioridade aparece sempre que algumas tarefas são mais importantes que outras. Um sistema operacional decide qual programa roda a seguir dando prioridade a processos críticos. Um servidor de tarefas pode marcar certos trabalhos como urgentes para que passem na frente da fila. Aplicativos de mensagem podem priorizar notificações importantes. E, num nível mais avançado, vários algoritmos de caminho, como os que encontram a rota mais curta num mapa com distâncias, usam uma fila de prioridade para escolher sempre o próximo ponto mais promissor. Você não vai implementar tudo isso agora, mas reconhecer que a estrutura por trás é uma fila de prioridade já muda a forma como você lê esses problemas.