Heaps e Filas de Prioridade

Uma fila de prioridade é um tipo de dado abstrato que sempre retorna o elemento de maior (ou menor) prioridade; heaps são as estruturas padrão baseadas em árvore que a implementam com operações eficientes de inserção e extração do mínimo.

Definition

Uma fila de prioridade é um tipo de dado abstrato que suporta a inserção de elementos com prioridades e a extração do elemento de maior prioridade; um heap é uma estrutura de dados baseada em árvore que satisfaz a propriedade de heap — a chave de cada nó é ordenada consistentemente em relação aos seus filhos — que implementa uma fila de prioridade de forma eficiente.

Scope

Este tópico aborda o ADT de fila de prioridade e suas implementações de heap: o heap binário e sua representação em array, a propriedade de heap e as operações sift-up/sift-down, heapsort, e heaps mescláveis avançados, como heaps binomiais e de Fibonacci, que melhoram os custos de diminuição de chave e união. Ele se conecta a algoritmos de grafo (Dijkstra, Prim) e simulação orientada a eventos, que dependem de filas de prioridade.

Core questions

• Quais operações definem o ADT de fila de prioridade e como um heap as implementa?
• Como a propriedade de heap permite encontrar o mínimo em tempo constante e inserir/extrair em tempo logarítmico?
• Como um heap binário é armazenado compactamente em um array, e como ele é construído em tempo linear?
• Como o heapsort usa um heap para ordenar in-place em tempo O(n log n)?
• Quando heaps mescláveis, como os heaps de Fibonacci, melhoram algoritmos que diminuem chaves frequentemente?

Key concepts

• ADT de fila de prioridade
• propriedade de heap
• heap binário
• representação de heap baseada em array
• sift-up e sift-down
• construção de heap em tempo linear
• heapsort
• heaps de Fibonacci e binomiais

Key theories

Propriedade de heap e representação em array

Um heap binário é uma árvore binária quase completa na qual a chave de cada nó domina as de seus filhos; ele pode ser armazenado em um array com indexação implícita pai-filho, resultando em inserção e extração O(log n) e busca do mínimo O(1).

Eficiência amortizada de heaps de Fibonacci

Heaps de Fibonacci suportam a operação decrease-key em tempo amortizado O(1) e extract-min em tempo amortizado O(log n), melhorando o tempo de execução assintótico de algoritmos como os de Dijkstra e Prim que realizam muitas diminuições de chave.

Clinical relevance

Filas de prioridade são infraestruturas essenciais: elas ordenam tarefas prontas em agendadores de sistemas operacionais, gerenciam eventos em simulação de eventos discretos, impulsionam a busca best-first e A*, e fornecem a fronteira nos algoritmos de Dijkstra e Prim. O Heapsort oferece uma ordenação in-place O(n log n) com limites garantidos para o pior caso.

History

J. W. J. Williams introduziu o heap binário e o heapsort em 1964, e Robert Floyd apresentou o procedimento de construção de heap em tempo linear pouco depois. Heaps binomiais (Vuillemin, 1978) e heaps de Fibonacci (Fredman e Tarjan, 1987) adicionaram fusão eficiente e diminuição de chave amortizada, aprimorando os tempos de execução de algoritmos clássicos de grafo.

Key figures

• J. W. J. Williams
• Robert W. Floyd
• Michael Fredman
• Robert Tarjan

Seminal works

• williams1964
• fredman1987
• cormen2009

Frequently asked questions

Por que armazenar um heap binário em um array em vez de usar ponteiros?

Um heap binário é uma árvore binária quase completa, então seus nós se mapeiam de forma limpa para índices consecutivos de um array: um nó no índice i tem filhos em 2i e 2i+1. Isso evita a sobrecarga de ponteiros, melhora o comportamento do cache e torna a navegação uma aritmética simples.

Quando os heaps de Fibonacci justificam sua complexidade?

Heaps de Fibonacci fornecem decrease-key amortizado O(1), o que melhora o tempo de execução assintótico de algoritmos como os de caminhos mais curtos de Dijkstra em grafos densos. Na prática, seus grandes fatores constantes significam que heaps binários mais simples são frequentemente mais rápidos, então eles são importantes principalmente para limites teóricos e casos especializados.