Heaps & Heapsort
Heap é uma estrutura de dados especial baseada em Árvore na qual a árvore é uma árvore binária completa e cada nó possuí uma chave atribuída
Tipos :
Max-Heap : a chave presente no nó raiz deve ser a maior entre as chaves presentes em todos os seus filhos
Min-Heap : a chave presente no nó raiz deve ser mínima entre as chaves presentes em todos os seus filhos
⚠ Exemplo
⚠ Exemplo de Uso :
Fila de Prioridade :
As filas prioritárias podem ser implementadas com eficiência usando Binary Heap porque ela oferece suporte a operações insert (), delete () e extractmax (), reduceKey () em tempo O (log (n))
Condições Importantes :
Prioridade de Forma : a árvore binária é essencialmente completa
Domínio Parental : a chave em cada nó é maior ou igual às chaves em seus filhos
Construção :
Bottom-up
Top-down
O algoritmo heapsort é um algoritmo de ordenação generalista, e faz parte da família de algoritmos de ordenação por seleção
Funcionamento :
Construa uma heap para uma determinada matriz
Aplicar a operação de exclusão de raiz n - 1 vezespara a pilha restante
⚠ Complexidade :
Possui complexidade (n log(n)) para todos os casos e complexidade O(1) de espaço. Não é estável
⚠ Obs: Tem eficiência semelhante ao Mergesort, mas tem melhor eficiência de espaço
Heapify após cada inserção
Pior eficiência temporal de cada inserção em O (log n)
Elementos inseridos um por um
Pior eficiência temporal de criação de heap em O (n log n)
Todos os elementos inseridos de uma vez
Heapify do último para o primeiro nó interno
Elementos conhecidos de antemão
Pior eficiência temporal de criação de heap em O (n)
Elementos não conhecidos de antemão