Hashing, ordenação e PriorityQueue em C#

Esta parte é sobre os contêineres, e sobre as partes da biblioteca padrão do C# que os materiais de maratona costumam errar porque são anteriores a elas.

Todo programa abaixo é completo, rodou no .NET 10, e a saída está colada da execução.

Padrão 26 — Contar coisas

Quatro jeitos, em ordem crescente de custo.

using System.Runtime.InteropServices;

int[] a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

// The version everyone writes. Two hash lookups per item.
Dictionary<int, int> plain = [];
foreach (int x in a) plain[x] = plain.GetValueOrDefault(x) + 1;

// One lookup. The ref points into the dictionary's own storage.
Dictionary<int, int> fast = [];
foreach (int x in a)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(fast, x, out _);
    slot++;
}

// .NET 9 and later. Shortest to write, allocates an enumerable.
var counted = a.CountBy(x => x).OrderBy(kv => kv.Key);

Console.WriteLine($"plain   : {string.Join(" ", plain.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"ref     : {string.Join(" ", fast.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"CountBy : {string.Join(" ", counted.Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"all agree: {plain.OrderBy(k => k.Key).SequenceEqual(fast.OrderBy(k => k.Key))}");

// When the keys are small and dense, skip hashing altogether.
int[] tally = new int[10];
foreach (int x in a) tally[x]++;
Console.WriteLine($"array   : [{string.Join(", ", tally)}]   <- no hashing at all");

Ele imprime:

plain   : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
ref     : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
CountBy : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
all agree: True
array   : [0, 2, 1, 2, 1, 3, 1, 0, 0, 1]   <- no hashing at all

dict[x] = dict.GetValueOrDefault(x) + 1 faz o hash da chave duas vezes — uma para ler, outra para escrever. CollectionsMarshal.GetValueRefOrAddDefault devolve um ref direto para o armazenamento do dicionário, então o incremento acontece in-place depois de um único lookup. Em um laço apertado sobre um milhão de itens isso é uma diferença real, e são três linhas.

CountBy chegou no .NET 9. É a coisa mais curta de escrever e aloca um enumerable, que é o trade-off certo fora de um laço quente.

E quando as chaves são inteiros pequenos e não negativos, um int[] simples ganha de todos. Sem hashing, sem colisões, memória contígua. Se o problema diz que os valores estão entre 1 e 10⁶, esse array tem 4MB e é quase certamente a resposta certa.

Use quando — sempre, mas escolha o certo. Chaves pequenas e densas pedem um array. Um laço quente pede o ref. Qualquer outra coisa, escreva o legível.

Padrão 27 — Agrupar por uma assinatura

Agrupe palavras que são anagramas umas das outras.

O padrão inteiro é escolher uma assinatura: algo idêntico para tudo dentro de um grupo e diferente para tudo fora dele.

string[] words = ["eat", "tea", "tan", "ate", "nat", "bat"];

// The signature has to be identical for anagrams and different for anything
// else. Sorted letters is the obvious one.
static string SortedKey(string w)
{
    char[] c = w.ToCharArray();
    Array.Sort(c);
    return new string(c);
}

// For a fixed alphabet, a count vector is O(n) instead of O(n log n).
static string CountKey(string w)
{
    int[] n = new int[26];
    foreach (char c in w) n[c - 'a']++;
    return string.Join(",", n);
}

foreach (var g in words.GroupBy(SortedKey))
    Console.WriteLine($"key \"{g.Key}\"  ->  [{string.Join(", ", g)}]");

Console.WriteLine();
Console.WriteLine($"both keys agree on the grouping: " +
    $"{words.GroupBy(SortedKey).Count() == words.GroupBy(CountKey).Count()}");
Console.WriteLine($"SortedKey(\"eat\") = \"{SortedKey("eat")}\"");
Console.WriteLine($"CountKey(\"eat\")  = \"{CountKey("eat")}\"");

Ele imprime:

key "aet"  ->  [eat, tea, ate]
key "ant"  ->  [tan, nat]
key "abt"  ->  [bat]

both keys agree on the grouping: True
SortedKey("eat") = "aet"
CountKey("eat")  = "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0"

As letras ordenadas são a assinatura óbvia e custam O(m log m) por palavra. Para um alfabeto fixo, a contagem de cada letra é O(m) e funciona igualmente bem — a saída confirma que as duas produzem o mesmo agrupamento.

Os casos interessantes são aqueles em que a assinatura óbvia está sutilmente errada. Para “essas duas árvores têm o mesmo formato”, a assinatura precisa codificar também os nulls, senão árvores diferentes colidem. Deixar a assinatura exatamente tão forte quanto a equivalência que você quer é o trabalho inteiro.

Use quando o problema diz agrupe, encontre duplicatas, ou quantos distintos.

Padrão 28 — Comparadores, e a ordenação que reordena itens iguais

Ordene por pontuação decrescente, depois por nome crescente.

(string Name, int Score)[] people =
[
    ("ada", 90), ("grace", 85), ("alan", 90), ("edsger", 85), ("barbara", 90)
];

// Score descending, then name ascending. One comparer, two keys.
var byScoreThenName = Comparer<(string Name, int Score)>.Create((x, y) =>
{
    int c = y.Score.CompareTo(x.Score);       // reversed operands = descending
    return c != 0 ? c : string.CompareOrdinal(x.Name, y.Name);
});

var arr = people.ToArray();
Array.Sort(arr, byScoreThenName);
foreach (var p in arr) Console.WriteLine($"  {p.Name,-8} {p.Score}");

// Array.Sort is NOT stable, and here is exactly where that starts to show.
Console.WriteLine($"\n{"n",4}  {"Array.Sort keeps input order?",32}");
foreach (int n in new[] { 8, 16, 17, 32 })
{
    var items = Enumerable.Range(0, n).Select(i => (Id: i, Key: i % 2)).ToArray();

    var viaSort = items.ToArray();
    Array.Sort(viaSort, (x, y) => x.Key.CompareTo(y.Key));

    var viaOrderBy = items.OrderBy(p => p.Key).ToArray();

    Console.WriteLine($"{n,4}  {viaSort.SequenceEqual(viaOrderBy),32}");
}

Console.WriteLine("\n.NET's introsort drops to insertion sort for 16 elements or fewer,");
Console.WriteLine("and insertion sort happens to be stable. At 17 it partitions, and does not.");

Ele imprime:

  ada      90
  alan     90
  barbara  90
  edsger   85
  grace    85

   n     Array.Sort keeps input order?
   8                              True
  16                              True
  17                             False
  32                             False

.NET's introsort drops to insertion sort for 16 elements or fewer,
and insertion sort happens to be stable. At 17 it partitions, and does not.

O comparador de várias chaves é rotina: compare pela primeira chave, e só caia para a segunda quando a primeira empata. Decrescente significa inverter os operandos — y.CompareTo(x) — não negar o resultado, o que quebra em int.MinValue.

A segunda metade é a parte que pega as pessoas.

Array.Sort não é estável. OrderBy é. E olhe onde isso começa a importar: n = 16 concorda, n = 17 não. O introsort do .NET cai para insertion sort em partições de 16 ou menos, e o insertion sort por acaso preserva a ordem. Acima disso ele particiona, e elementos iguais se movem.

Um bug de estabilidade passa limpo em dezesseis itens e falha em dezessete. Esse não é um tamanho que alguém escolhe para um caso de teste.

Se a ordem entre itens iguais importa, use OrderBy/ThenBy, ou adicione um critério de desempate ao comparador para que dois itens nunca comparem iguais. O segundo é o que o código de maratona faz, porque Array.Sort em um array cru é mais rápido e não aloca nada.

Use quando ordenar por qualquer coisa que não seja a ordem natural. E sempre que elementos iguais precisarem manter a ordem de entrada.

Padrão 29 — Compressão de coordenadas

Valores até um milhão, mas só um punhado deles distintos. Você quer um array indexado por valor, e ele precisaria de um milhão de células.

Os valores só estão sendo comparados. Então jogue-os fora e fique com os ranks deles.

int[] a = [1_000_000, 5, 300, 5, 99_999, 300];

// The values matter only by their ORDER, so replace each with its rank.
int[] sorted = a.Distinct().Order().ToArray();
Dictionary<int, int> rank = sorted
    .Select((v, i) => (v, i))
    .ToDictionary(t => t.v, t => t.i);

int[] compressed = a.Select(v => rank[v]).ToArray();

Console.WriteLine($"original   : [{string.Join(", ", a)}]");
Console.WriteLine($"distinct   : [{string.Join(", ", sorted)}]");
Console.WriteLine($"compressed : [{string.Join(", ", compressed)}]");
Console.WriteLine();
Console.WriteLine($"an array indexed by value would need {a.Max() + 1:N0} cells");
Console.WriteLine($"an array indexed by rank needs      {sorted.Length:N0}");
Console.WriteLine();

// Order is preserved, which is the only property that had to survive.
for (int i = 0; i < a.Length; i++)
    for (int j = 0; j < a.Length; j++)
        if (a[i].CompareTo(a[j]) != compressed[i].CompareTo(compressed[j]))
            throw new Exception("order not preserved");
Console.WriteLine("every pairwise comparison gives the same answer as before: True");

// And it is reversible.
Console.WriteLine($"decompressed: [{string.Join(", ", compressed.Select(r => sorted[r]))}]");

Ele imprime:

original   : [1000000, 5, 300, 5, 99999, 300]
distinct   : [5, 300, 99999, 1000000]
compressed : [3, 0, 1, 0, 2, 1]

an array indexed by value would need 1,000,001 cells
an array indexed by rank needs      4

every pairwise comparison gives the same answer as before: True
decompressed: [1000000, 5, 300, 5, 99999, 300]

A verificação no meio é a justificativa inteira: toda comparação entre pares dá a mesma resposta depois da compressão e antes dela. Nada de que o algoritmo dependia foi perdido. E a última linha mostra que é reversível — guarde o array de distintos ordenado e você mapeia qualquer rank de volta.

Custo: O(n log n) para a ordenação, O(n) depois.

Use quando os valores são enormes ou esparsos mas a quantidade deles é pequena — segment trees sobre coordenadas, linhas de varredura, “contar distintos em um intervalo”, qualquer coisa com timestamps.

Padrão 30 — PriorityQueue<TElement, TPriority>

Isso chegou no .NET 6. Muito material de programação competitiva em C# é mais antigo, e contorna a ausência dele com um SortedSet e uma chave de desempate. Isso não é mais necessário.

Duas coisas sobre ele valem saber antes de você usar.

Ele é um min-heap: a menor prioridade sai primeiro. E o elemento é separado da prioridade, que é o que deixa o Dijkstra da parte 8 legível — você enfileira um nó com uma distância, em vez de empacotar os dois em uma tupla e escrever um comparador.

Para ficar com os k maiores valores, use um min-heap de tamanho k. Isso soa invertido e não é: a raiz é o mais fraco dos seus sobreviventes atuais, que é exatamente o valor que um recém-chegado tem que superar, e o único contra o qual vale comparar.

int[] a = [5, 1, 9, 3, 7, 2, 8];
int k = 3;

// PriorityQueue is a MIN-heap: the smallest priority comes out first.
// To keep the k LARGEST, hold a min-heap of size k and evict its smallest.
PriorityQueue<int, int> topK = new();

foreach (int x in a)
{
    if (topK.Count < k)
    {
        topK.Enqueue(x, x);
        Console.WriteLine($"{x}  heap not full, keep it        -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else if (x > topK.Peek())
    {
        // One operation instead of Dequeue then Enqueue: one sift, not two.
        int evicted = topK.EnqueueDequeue(x, x);
        Console.WriteLine($"{x}  beats the smallest ({evicted}), swap  -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else
    {
        Console.WriteLine($"{x}  loses to the smallest ({topK.Peek()})   -> unchanged");
    }
}

List<int> result = [];
while (topK.Count > 0) result.Add(topK.Dequeue());
Console.WriteLine($"\ntop {k} largest, ascending: [{string.Join(", ", result)}]");

// Priority and element are separate, which is what makes Dijkstra readable.
PriorityQueue<string, int> tasks = new();
tasks.Enqueue("write tests", 2);
tasks.Enqueue("fix the bug", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine();
while (tasks.TryDequeue(out string? task, out int p))
    Console.WriteLine($"  priority {p}: {task}");

Ele imprime:

5  heap not full, keep it        -> [5]
1  heap not full, keep it        -> [1,5]
9  heap not full, keep it        -> [1,5,9]
3  beats the smallest (1), swap  -> [3,5,9]
7  beats the smallest (3), swap  -> [5,7,9]
2  loses to the smallest (5)   -> unchanged
8  beats the smallest (5), swap  -> [7,8,9]

top 3 largest, ascending: [7, 8, 9]

  priority 1: fix the bug
  priority 2: write tests
  priority 3: refactor

EnqueueDequeue é o detalhe que vale roubar. Empurrar e depois tirar faz o sift do heap duas vezes; EnqueueDequeue faz em uma só, porque ele sabe que o novo elemento vai ser comparado com a raiz de qualquer jeito.

Duas coisas que ele não tem. Não existe DecreaseKey, e é por isso que o Dijkstra em C# usa a abordagem preguiçosa — empurra duplicatas, pula as obsoletas na saída. E UnorderedItems é exatamente o que diz: ordem de heap, não ordem ordenada. Serve para inspecionar, é inútil para saída.

Custo: O(log n) por push e pop, O(n) de espaço. Top-k sobre n itens é O(n log k).

Use quando você precisa de “o menor que resta” repetidamente — Dijkstra, k-way merge, escalonamento de tarefas, top-k.

O que lembrar

• GetValueOrDefault e depois atribuir faz o hash da chave duas vezes. CollectionsMarshal.GetValueRefOrAddDefault faz uma vez só e devolve um ref.

• Chaves inteiras pequenas e densas não precisam de dicionário. Um int[] é mais rápido, mais simples, e geralmente a solução pretendida.

• Um agrupamento vale o que vale a assinatura dele. Ela tem que ser idêntica dentro de um grupo e diferente fora dele — nem mais fraca, nem mais forte.

• Decrescente significa inverter os operandos, não negar o resultado. A negação quebra em int.MinValue.

• Array.Sort é instável acima de 16 elementos. Exatamente 16 é estável por acidente. Use OrderBy, ou torne os empates impossíveis com uma chave de desempate.

• A compressão mantém a ordem e descarta a magnitude, que é tudo o que esses problemas usavam. Guarde o array de distintos ordenado e ela é reversível.

• PriorityQueue é um min-heap, e para os k maiores é isso que você quer. Use EnqueueDequeue para fazer o sift uma vez em vez de duas, e lembre que não existe DecreaseKey.

A parte 7 começa nos grafos, e abre com a representação — porque List<List<int>> é o que a maioria das soluções de maratona em C# usa, e é também por que elas estouram o limite de tempo.