GabaritoD — Heap binário.
Gabarito: letra D. Heap binário é a estrutura de dados mais eficiente para implementar uma fila de prioridades, pois permite inserir e remover o elemento de maior prioridade em tempo O(log n), enquanto estruturas lineares como listas encadeadas, pilhas e filas circulares exigem O(n) ou não atendem ao requisito de prioridade.
A fila de prioridades é um tipo abstrato de dados onde cada elemento possui uma prioridade, e a operação de remoção sempre retorna o elemento de maior prioridade. Para ser eficiente, é necessário um suporte que mantenha a ordenação implícita ou explícita com baixo custo.
A tabela a seguir compara as alternativas quanto à complexidade das operações principais:
Estrutura | Inserção | Remoção do máximo | Observação |
|---|---|---|---|
Lista encadeada simples | O(1) no início/fim | O(n) para encontrar o maior | Sem ordenação por prioridade |
Pilha | O(1) (push) | O(1) (pop) – mas remove o último inserido | Não considera prioridade |
Fila circular | O(1) (enqueue) | O(1) (dequeue) – mas remove o primeiro inserido | Não considera prioridade |
Heap binário | O(log n) | O(log n) | Mantém a propriedade de heap; ideal para fila de prioridades |
Matriz bidimensional | O(1) (se índice conhecido) | Ineficiente – seria necessário percorrer toda a matriz | Não projetada para prioridade |
A lista encadeada simples não possui acesso direto ao elemento de maior prioridade. Para removê-lo, seria necessário percorrer toda a lista (O(n)) para localizá-lo, o que é ineficiente comparado à heap. Inserções podem ser O(1), mas a remoção do máximo é cara.
A pilha opera com a política LIFO (Last In, First Out), ou seja, remove sempre o elemento mais recentemente inserido, independentemente de prioridade. Não atende ao requisito de remover o de maior prioridade.
A fila circular segue a política FIFO (First In, First Out), removendo o elemento que está na fila há mais tempo. Não há qualquer noção de prioridade. Portanto, não serve para uma fila de prioridades.
O heap binário é uma árvore binária (quase completa) que satisfaz a propriedade de heap: em um max-heap, cada nó pai é maior ou igual a seus filhos. Isso garante que o maior elemento esteja sempre na raiz. Tanto a inserção quanto a remoção do máximo têm complexidade O(log n), sendo a estrutura clássica e mais eficiente para filas de prioridades.
Matriz bidimensional é uma estrutura tabular usada para representar dados em linhas e colunas. Não oferece suporte natural a operações de fila com prioridade; seria necessário percorrer todos os elementos para encontrar o maior, resultando em O(n*m).
Lembre-se de que fila de prioridades não é uma fila comum (FIFO). A implementação clássica é o heap binário, que você pode visualizar como uma árvore. Na prova, distinga fila de prioridades de fila comum – a banca pode tentar confundir com opções como 'fila circular'.
Gabarito: letra D.
Link permanente: /questoes/qg510937