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