Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10 - Coggle Diagram
M10
Noções de Heap
Um heap pode ser definido como uma árvore binária com chaves atribuídas aos seus nós, uma chave por nó, desde que as duas condições a seguir sejam atendidas:
- A propriedade da forma – a árvore binária está essencialmente completa (ou simplesmente completa), ou seja, todos os seus níveis estão cheios, exceto possivelmente o último nível, onde apenas algumas folhas mais à direita podem estar faltando.
- A dominância parental ou propriedade de heap – a chave em cada nó é maior ou igual às chaves de seus filhos. (Esta condição é considerada automaticamente satisfeita para todas as folhas.)5
Por exemplo, considere as árvores da Figura 6.9. A primeira árvore é uma pilha.
Relacionamento entre valores-chave para nós no mesmo nível da árvore ou, mais geralmente, nas subárvores esquerda e direita do mesmo nó.
Heapsort
Os elementos da matriz são eliminados em ordem decrescente. Mas como na implementação de array de heaps um elemento que está sendo excluído é colocado por último, o array resultante será exatamente o array original classificado em ordem crescente.
“heap” definitivamente não é uma pilha desordenada de itens como a definição da palavra em um dicionário padrão pode sugerir.
é uma estrutura de dados inteligente e parcialmente ordenada, especialmente adequada para implementar filas prioritárias.
uma fila de prioridade é um multiconjunto de itens com uma característica solicitável chamada prioridade de item.
1 - encontrar um item com a prioridade mais alta (ou seja, maior).
2 - excluir um item com a prioridade mais alta.
3 - adicionando um novo item ao multiset.
É principalmente uma implementação eficiente dessas operações que torna o heap interessante e útil.
As filas prioritárias surgem naturalmente em aplicações como agendamento de execuções de tarefas por sistemas operacionais de computadores e gerenciamento de tráfego por redes de comunicação.
RESUMO
Heap é uma árvore binária que obedece a duas condições:
1° propiedade de forma , é uma árvore binária completa os elementos são inseridos de cima para baixo e da esquerda para a direita.
2° propiedade de dominância parental, para qualquer nó da heap esse nó precisa ser maior ou igual do que os seus filhos, sendo uma heap máxima.
para qualquer nó de uma heap sendo menor ou igual que os seus filhos é uma heap mínima.
Diferente de uma BST ONDE TEM UMA ORDEM ENTRE OS FILHOS, os nós das sub árvores a esquerda e os nós da sub arvores a direita são maiores ou iguais. Na Heap a única coisa que precisa acontecer é que o nó deve ser maior ou igual que os filhos.
-