Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps - Coggle Diagram
Heaps
Árvore binária que com keys associadas a cada nó
Árvore binária completa todos os níveis da árvore estão
totalmente ocupados com exceção do último que pode estar parcialmente cheio
A key de cada nó é maior ou igual que as keys dos nós inferiores
Propriedades
Uma heap de n nós só é essencialmente de completa se a altura for igual a log de n na base 2
A raiz sempre é o maior elemento
Um nó de uma heap com todos seus descendentes também é considerado uma heap
Pode ser implementada por array
Primeiro elemento na posição 1 do array
O nó pai de um nó na posição nserá o nó na posição n/2
Nó filhos de um nó n ocuparão as posições 2n e 2n+1
Implementação BottomUP
Inserir
for(int i=n/2;i>=1)
int k=i
int v=H[k]
boolean heap =false
while(!heap && 2*k<=n)
int J =2*k
if (J<n)
if (H [J ] < H [J + 1])
J++
if (v ≥ H [J ])
heap=true
else
H [k] = H [ J ]
k=j
H[k]=v
H[n]
Eficiência de uma inserção e remoção
O(log n)
Remover um item
Trocar o item que deseja remover com o último
Diminuir o tamanho em 1
Trocar o elemento que está agora na raiz com o maior dos seus filhos e checar se a heap está balanceada caso contrario continue trocando com os maiores filhos
Heap Sort
Transfrome o array em uma heap
Executa a operação de deetar elementos n-1 vezes
Eficiência Θ(n log n)