Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap, Algoritmos de Construção de Heap - Coggle Diagram
Heap
Implementação do Heap
Armazenamento dos elementos em um array de forma top-down e da esquerda para a direita
Relações de posição:
Pais ocupam as primeiras n/2 posições
Filhos nas posições 2i e 2i+1
Pais na posição i/2
Propriedades Importantes do Heap
Existe exatamente uma árvore binária essencialmente completa com n nós
A raiz do heap sempre contém seu maior elemento
Um nó considerado com todos os seus descendentes também é um heap
Implementação do heap como um array
Propriedades do Heap
Propriedade de Forma: Árvore binária essencialmente completa
Propriedade de Dominância Parental: Chave em cada nó é maior ou igual às chaves de seus filhos
Árvore Binária
Chaves atribuídas aos nós
Algoritmos de Construção de Heap
Algoritmo Bottom-Up
Inicializa a árvore essencialmente completa com n nós
"Heapifica" a árvore começando do último nó parental
Verifica a dominância parental
Troca a chave do nó com a maior chave dos filhos, se necessário
Repete até que a dominância parental seja satisfeita