Please enable JavaScript.
Coggle requires JavaScript to display documents.
HEAPS - Coggle Diagram
HEAPS
Semanticamente equivalentes a árvores binárias com propriedades específicas
Propriedades que definem uma heap
Valor/elemento/chave associado a um nódulo pai é maior do que o associado a seus filhos
Em caso da árvore não ser completa, a disposição dos nódulos no último nível prioriza as posições mais à esquerda
Todos os níveis exceto o último estão obrigatoriamente completos
Existe um único formato de heap de n nódulos, sua altura é ⌊log2 n⌋
A raiz da heap contém seu maior elemento/chave
Um nódulo de heap + seus decendentes também é uma heap
Implementados mais eficientemente através de arrays
Propriedades da representação por array de uma heap
Dispõe os elementos no sentido cima-baixo e esquerda-direita tendo como base as posições que eles teriam numa heap árvore
É útil a disposição dos elementos no intervalo A[ 1 ] até A[ n ], deixando a posição 0 do array de fora. Isto é feito para alcançar as propriedades abaixo
Os nódulos parentais ocupam as primeiras ⌊n/2⌋posições enquanto as folhas ocupam as últimas ⌈n/2⌉ posições
Os filhos de um nódulo parental na posição i estarão nas posições 2i e 2i+1 respectivamente, enquanto os pais de um nódulo na posição i estará na posição i/2
OPERAÇÕES
Encontrar o elemento de maior prioridade
Inserir um elemento
Deletar o elemento com maior prioridade
Construção de uma heap
HEAPSORT
Baixo pra cima
Cima pra baixo
Remoção de elementos de uma heap
Normalmente atua no maior elemento
Em um array heap, muda a posição do nódulo para o final do array e diminui seu tamanho