Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap - Coggle Diagram
Heap
Heap sort
-
-
Eficiência - 0(nlogn) (no mesmo nível do mergesort, pior que quicksort)
-
-
- A árvore é completa se todos os níveis estão cheios, exceto o último nível que pode ter a folha a direita faltando
- A chave nos nós pais são maiores ou iguais aos dos filhos
Operações
- Achar o item na prioridade mais alta
- Deletar o item na prioridade mais alta
- Adicionar um item no conjunto
Bottom-up
Começa do último nó adicionado e checa os filhos, caso o pai seja menor que o filho então eles trocam de posição e continua subindo de nível até chegar na raiz
-
-
Deletar - O nó a ser deletado é trocado com o menor nó, excluído e depois são feitas as operações necessárias para que a heap atenda suas propriedades. (o pior caso é deletar a raiz, e nesse caso, diminuir 1 da altura da árvore)
-
É uma estrutura de dados parcialmente ordenada feita para implementação de filas prioritárias. É uma árvore binária com chaves associadas ao seus nós.
-
-
-
No array da heap todos os elementos na posição i na primeira metade do array são maiores ou iguais aos da posição 2i e 2i+1