Pilhas, Filas, Heaps e Contêineres Associativos: o Estado que Sobrevive à Pergunta Seguinte

O Artigo 17 fechou o capítulo dos arrays com um treino em que nada mudava depois de lido: os canais eram dragados no fim, as profundidades do rio estavam registradas para sempre, e os pedidos do banco de sementes chegavam todos de uma vez. Este artigo abre o capítulo das estruturas de dados, que trata do mundo em que os valores mudam enquanto as perguntas chegam. O livro define uma estrutura de dados como um acordo entre as atualizações e as perguntas: ela guarda informação suficiente para não recomeçar do zero, mas não tanta que cada atualização vire uma tragédia.

Com $n=q={10}^5$, uma estrutura que paga $O(n)$ por operação faz ${10}^{10}$ passos. As estruturas deste capítulo trocam memória e complexidade de implementação por custos menores por operação:

Tabela 1: As estruturas do capítulo e os seus custos.

Este artigo trata das quatro primeiras famílias que não dependem de árvores especiais: pilhas e filas, árvores ordenadas, heaps e hash tables (tabelas indexadas por uma função de hash). A árvore de Fenwick e a segment tree (árvore que guarda resumos de intervalos) ficam para o Artigo 19, e os conjuntos disjuntos, para o Artigo 20.

As medições foram feitas com o MSVC do Visual Studio 18.10.3, com /std:c++latest /O2, em um Intel Core i7-10750H. Cada tempo é a mediana de cinco execuções depois de uma de aquecimento, salvo onde o texto disser outra coisa. Os programas deste artigo, com as entradas e as saídas esperadas de cada caso de teste, estão em serie-blog/competitiva-18.