Aprender algoritmos

Capítulo 4. Heaping It On

Este trabalho foi traduzido com recurso a IA. Agradecemos o teu feedback e comentários: [e-mail]

Neste capítulo, aprenderás:

• Os tipos de dados fila e fila prioritária.

• A estrutura de dados heap binária, inventada em 1964, que pode ser armazenada numa matriz.

• Que num heap binário máximo, uma entrada com uma prioridade numérica maior é considerada como tendo maior prioridade do que uma entrada com uma prioridade numérica menor. Num heap binário mínimo, as entradas com prioridade numérica menor têm prioridade mais elevada.

• Como colocar uma entrada (valor, prioridade) numa heap binária em O(log N), onde N é o número de entradas na heap.

• Como encontrar o valor com maior prioridade num heap binário em O(1).

• Como remover o valor com maior prioridade de um heap binário em O(log N).

Em vez de armazenares apenas uma coleção de valores, e se armazenasses uma coleção de entradas, em que cada entrada tem um valor e umaprioridade associada representada por um número? Dadas duas entradas, aquela cuja prioridade é maior é mais importante do que a outra. O desafio desta vez é tornar possível inserir novas entradas (valor, prioridade) numa coleção e ser capaz de remover e devolver o valor da entrada com maior prioridade da coleção.

Esse comportamento define uma fila de prioridades - umtipo de dados que suporta eficientemente enqueue(value, priority) e dequeue(), que remove o valor com a prioridade mais alta. A fila de prioridades ...