Priority Queue

O que é uma Priority Queue

Uma fila tradicional segue o modelo FIFO, sigla em inglês para "o primeiro a entrar é o primeiro a sair". Ou seja, o item mais antigo sempre sai antes dos demais.

A Priority Queue muda essa regra. Cada item entra acompanhado de uma prioridade, e a fila sempre entrega primeiro o item com o menor valor de prioridade.

No .NET, a classe se chama PriorityQueue<TElement, TPriority> e fica no namespace System.Collections.Generic. Por isso, você não precisa instalar nenhum pacote extra para utilizá-la.

O primeiro parâmetro genérico, TElement, representa o tipo do item armazenado. O segundo, TPriority, representa o tipo da prioridade associada a cada item.

Antes do .NET 6, quem precisava de uma fila de prioridade costumava escrever a própria implementação ou recorrer a bibliotecas de terceiros. Com a chegada do tipo nativo, essa necessidade praticamente desapareceu.

Se quiser conhecer outras novidades daquela geração da plataforma, vale ler o artigo sobre as novidades do .NET 6 Preview 1.

Como a Priority Queue funciona por dentro

Segundo a documentação oficial da classe PriorityQueue, a implementação usa um min-heap quaternário apoiado em um array. Em outras palavras, cada nó da árvore tem até quatro filhos, e o menor valor sempre fica no topo.

Essa estrutura explica o desempenho da Priority Queue. Inserir e remover itens custa tempo logarítmico, pois a fila só reorganiza um caminho da árvore em cada operação.

Consultar o próximo item, por outro lado, custa tempo constante. Afinal, ele está sempre na raiz do heap.

Existe, porém, um detalhe importante. A documentação avisa que a classe não garante a ordem de chegada para itens com a mesma prioridade, então dois itens empatados podem sair em qualquer ordem.

Mais adiante, você verá uma técnica simples para resolver esse empate quando a ordem de chegada importar.

Criando uma Priority Queue no C#

A forma mais simples de criar uma Priority Queue é usar o construtor sem parâmetros. Nesse caso, a fila usa o comparador padrão do tipo da prioridade.

var queue = new PriorityQueue<string, int>();

Neste exemplo, a fila armazena itens do tipo string, e a ordenação usa um inteiro (int) como prioridade. Como o comparador padrão de int ordena do menor para o maior, o item com prioridade 0 sai antes do item com prioridade 4.

Além desse construtor, a classe oferece sobrecargas que recebem uma capacidade inicial, um comparador customizado ou uma coleção de pares já prontos. Assim, você ajusta a criação da fila ao cenário de uso.

queue.Enqueue("Item 1", 0);
queue.Enqueue("Item 2", 4);
queue.Enqueue("Item 3", 2);
queue.Enqueue("Item 4", 1);

queue.EnqueueRange(new[]
{
    ("Item 5", 3),
    ("Item 6", 5)
});

var queue = new PriorityQueue<string, int>();

queue.Enqueue("Item 1", 0);
queue.Enqueue("Item 2", 4);
queue.Enqueue("Item 3", 2);
queue.Enqueue("Item 4", 1);

// Remove sempre o item de menor prioridade
while (queue.TryDequeue(out var item, out var priority))
    Console.WriteLine($"Item: {item}. Priority: {priority}");

Item: Item 1. Priority: 0
Item: Item 4. Priority: 1
Item: Item 3. Priority: 2
Item: Item 2. Priority: 4

Outros métodos úteis da classe

Além de Enqueue e TryDequeue, a classe traz um conjunto pequeno, porém completo, de operações. Conhecer cada uma evita código desnecessário.

O método Dequeue remove e devolve o próximo item, mas lança InvalidOperationException quando a fila está vazia. Portanto, prefira TryDequeue quando não tiver certeza de que existem itens.

Já o método Peek devolve o próximo item sem removê-lo. Da mesma forma, o TryPeek faz a mesma consulta e também informa a prioridade, sem lançar exceção quando a fila está vazia.

// Consulta o próximo item sem removê-lo da fila
if (queue.TryPeek(out var next, out var nextPriority))
    Console.WriteLine($"Next: {next} ({nextPriority})");

A propriedade Count informa quantos itens a fila contém, enquanto o método Clear remove todos eles. Além disso, EnsureCapacity e TrimExcess ajudam a controlar a memória do array interno.

Há também o método EnqueueDequeue, que insere um item e logo em seguida remove o menor. Segundo a documentação, essa operação combinada costuma ser mais eficiente do que chamar os dois métodos em sequência.

Por fim, a propriedade UnorderedItems permite enumerar os itens sem removê-los. No entanto, como o próprio nome indica, essa enumeração não segue a ordem de prioridade.

Customizando a prioridade

No cenário anterior, a fila aplicou a ordenação padrão do .NET para inteiros, que sempre vai do menor para o maior. Como a prioridade era um int, os itens saíram de 0 a 4.

// int é o tipo da prioridade
var queue = new PriorityQueue<string, int>();

Muitas vezes, porém, você quer o comportamento oposto, em que o maior número representa a maior urgência. Nesse caso, basta informar um comparador que inverta a comparação padrão.

// Inverte a ordem: maiores prioridades saem primeiro
var maxQueue = new PriorityQueue<string, int>(
    Comparer<int>.Create((a, b) => b.CompareTo(a)));

maxQueue.Enqueue("Low", 1);
maxQueue.Enqueue("High", 10);
maxQueue.Enqueue("Medium", 5);

while (maxQueue.TryDequeue(out var item, out var priority))
    Console.WriteLine($"{item}: {priority}");

Com esse ajuste, a Priority Queue passa a funcionar como um max-heap. Assim, o item "High" sai primeiro, seguido de "Medium" e "Low".

public record Student(string Name);

public class RoleComparer : IComparer<string>
{
    // Quanto menor a posição, maior a prioridade
    private static int Rank(string? role) => role switch
    {
        "admin" => 0,
        "premium" => 1,
        _ => 2
    };

    public int Compare(string? roleA, string? roleB)
        => Rank(roleA).CompareTo(Rank(roleB));
}

var queue = new PriorityQueue<Student, string>(new RoleComparer());

queue.Enqueue(new Student("Spiderman"), "student");
queue.Enqueue(new Student("Ironman"), "premium");
queue.Enqueue(new Student("Batman"), "admin");

while (queue.TryDequeue(out var item, out var priority))
    Console.WriteLine($"Student: {item.Name}. Priority: {priority}");

Student: Batman. Priority: admin
Student: Ironman. Priority: premium
Student: Spiderman. Priority: student

Mantendo a ordem de chegada em empates

Como você viu, a documentação não garante a ordem de chegada entre itens com a mesma prioridade. Em uma fila de atendimento, porém, dois clientes premium normalmente esperam ser atendidos na ordem em que chegaram.

A solução mais comum é compor a prioridade com um contador sequencial. Assim, quando duas prioridades empatam, o contador desempata a favor do item mais antigo.

var queue = new PriorityQueue<string, (int Level, long Sequence)>();
long sequence = 0;

// O contador desempata itens com o mesmo nível
queue.Enqueue("First premium", (1, sequence++));
queue.Enqueue("Admin", (0, sequence++));
queue.Enqueue("Second premium", (1, sequence++));

while (queue.TryDequeue(out var item, out _))
    Console.WriteLine(item);

Nesse exemplo, a prioridade é uma tupla. O comparador padrão de tuplas compara primeiro o nível e, em caso de empate, a sequência.

Portanto, a saída mostra "Admin", depois "First premium" e por fim "Second premium". Com isso, a fila fica estável sem nenhum comparador extra.

Quando usar uma Priority Queue

A Priority Queue brilha sempre que você precisa processar primeiro o que é mais urgente, sem ordenar a coleção inteira a cada inserção. Alguns cenários aparecem com frequência.

O primeiro é o agendamento de tarefas, em que trabalhos críticos furam a fila de trabalhos rotineiros. Se esse processamento roda em segundo plano, o artigo sobre background services em C# e .NET mostra onde encaixar esse tipo de fila.

O segundo é a seleção dos K maiores ou menores itens de uma sequência grande. Nesse caso, você mantém uma fila com no máximo K elementos e descarta o menor sempre que ela passa do limite.

// Mantém apenas os três maiores valores
var top = new PriorityQueue<int, int>();

foreach (var value in new[] { 7, 2, 9, 4, 11, 5 })
{
    top.Enqueue(value, value);

    if (top.Count > 3)
        top.Dequeue();
}

Ao final do laço, a fila contém apenas 7, 9 e 11. Dessa forma, a memória cresce com K, e não com o tamanho da sequência.

O terceiro cenário envolve algoritmos de grafos, como o de Dijkstra para caminhos mínimos. Esse algoritmo sempre expande o nó com a menor distância conhecida, o que combina perfeitamente com um min-heap.

Cuidados ao usar a Priority Queue

Alguns detalhes evitam surpresas em produção. Primeiro, a classe não oferece sincronização interna, assim como as demais coleções genéricas comuns do namespace System.Collections.Generic.

Portanto, se várias threads acessam a mesma fila, você precisa proteger as operações com um mecanismo de exclusão. O artigo sobre controle de concorrência com Semaphore e SemaphoreSlim explica bem essas opções.

Em segundo lugar, no .NET 6 a classe não permite alterar a prioridade de um item que já está na fila. Se a prioridade mudar, a saída costuma ser enfileirar o item novamente e ignorar a versão antiga quando ela sair.

As notas de lançamento do .NET 9 confirmam essa limitação, já que essa versão acrescentou um método Remove justamente para emular atualizações de prioridade. Ainda assim, mesmo esse recurso custa tempo linear.

Em terceiro lugar, lembre que UnorderedItems não segue a prioridade. Então, nunca use essa propriedade para exibir a fila ordenada ao usuário.

Por fim, evite comparadores que leiam estado mutável. Se a regra de comparação mudar depois que os itens entraram, o heap perde a consistência e a ordem de saída deixa de fazer sentido.

Priority Queue ou outras coleções

Vale comparar a Priority Queue com outras opções do C# antes de escolher. Uma List<T> ordenada a cada inserção resolve o problema, mas paga o custo de reorganizar a lista inteira com frequência.

O SortedSet<T>, por sua vez, mantém os itens sempre ordenados e permite percorrê-los em ordem. Contudo, ele não aceita itens duplicados, o que complica cenários com prioridades repetidas.

Já a Queue<T> tradicional entrega apenas a ordem de chegada. Se a ordem de chegada basta, ela continua sendo a escolha mais simples.

Para filas consumidas por produtores e consumidores em paralelo, o System.Threading.Channels costuma ser mais adequado. O artigo sobre Channels em C# para APIs de alto volume detalha esse modelo.

Conclusão

O C# oferece um enorme leque de formas para trabalhar com listas e filas. É muito comum usar List<T> e IEnumerable<T> e esquecer de outros tipos, como a Priority Queue.

Com ela, você enfileira itens com uma prioridade, desenfileira sempre o mais importante e customiza a regra de ordenação com um IComparer<T>. Além disso, técnicas simples, como a prioridade em tupla, resolvem empates sem esforço.

Conhecer bem esses tipos amplia o seu repertório de soluções. Assim, na próxima vez que precisar processar itens por urgência, a Priority Queue estará pronta para ajudar.

FAQ

Em qual versão a Priority Queue chegou ao .NET?

A classe PriorityQueue<TElement, TPriority> chegou no .NET 6, lançado junto com o C# 10. Ela fica no namespace System.Collections.Generic.

A Priority Queue entrega primeiro o menor ou o maior valor?

Por padrão, ela entrega primeiro o menor valor de prioridade. Para inverter, informe um comparador que inverta a comparação, como Comparer<int>.Create((a, b) => b.CompareTo(a)).

Itens com a mesma prioridade saem na ordem de chegada?

Não há garantia disso. Para manter a ordem de chegada, use uma prioridade composta com um contador sequencial.

A Priority Queue é thread-safe?

Não. Se várias threads acessam a mesma instância, proteja as operações com um mecanismo de sincronização.

Qual a diferença entre Dequeue e TryDequeue?

O Dequeue lança InvalidOperationException quando a fila está vazia. Já o TryDequeue apenas retorna false, o que facilita o uso em laços.