Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap - Coggle Diagram
Heap
Operações
Achar tem com maior prioridade
Deletar item com maior prioridade
Adicionar um novo item
Regras
Árvore binária com uma chave designada para cada nó
Árvore completa (só o último nível pode estar sem algumas folhas)
Altura = log n
Um nó deve ter a chave >= às dos seus ramos
A raiz sempre tem o maior número
Usos
Heapsort (algoritmo de ordenação)
Construção da Heap
Vai deletando os elementos
São posicionados no final
Resulta na Array ordenada
Saem em ordem decrescente
Caso médio e pior: θ(n log n).
Eficiência semelhante ao do mergesort
Não precisa de armazenamento extra
Mais devagar que o quicksort
Ordem de execução no SO
Gerenciamento do tráfego no sistema de comunicação
Implementação por Array
Parents na primeira metade e ramos na segunda metade da Array
Gravar os elementos de cima para baixo da esquerda para direita
O valor do índice 0 deve ser vazio ou maior que todos (sentinela)
Deletar
Troca a raiz pela última chave
Diminui em um o tamanho da heap
Organiza o menor (Heapify)
Eficiência depende do número de trocas
O(log n)
Parcialmente ordenada
Útil para implementação de fila com prioridade
Eficiente
Bottom-up
Inicializa a árvore binária com as chaves na ordem dada
Depois organiza
Checa o parental node
Se não houver dominância, realiza a troca
O(n)
Recursivo até a raiz
Top-down
Menos eficiente
Insere uma chave e já organiza
Inserção: O(log n)
Número de comparações não pode ser maior que a altura