Please enable JavaScript.
Coggle requires JavaScript to display documents.
HEAPS, Propriedades, Exclusão Maxima de Chaves de uma Heap, HEAPSORT,…
HEAPS
Estrutura de dados inteligente e parcialmente ordenada, adequada para implementar filas prioritarias
Suas operaçoes principais são:
- Achar um item com maior prioridade
- Remover um item com menor prioridade
- Adicionar um item
Arvore binaria com chaves atribuidas aos seus nós (uma chave por nó), desde que as seguintes condições sejam atendidas:
- Arvore binaria completa, com todos os seus níveis preenchidos, exceto o ultimo nivel, que pode ter algumas folhar à direita faltando
- A chave em cada nó dos pais precisa ser maior que a dos filhos
-
-
-
-
Propriedades
-
-
-
-
Caso seja implementada como uma matriz, coloca na posição 0 um elemento maior do que qualquer um que pode ser adicionado na heap, e começa a adicionar da posição 1
-
-
Construção
BOTTOM-UP
- Construção de pilha de baixo para cima
- Inicializa a arvore binaria completa com n nós, colocando as chaves na ordem fornecida e heapfica a arvore começando com o ultimo no parental
- Bottom up é mais eficiente
TOP DOWN
- Inserções sucessivas de uma nova chave em um heap