Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps, Heap Máximo: pai ≥ filhos, Heap Mínimo: pai ≤ filhos - Coggle…
Heaps
Estrutura de dados em árvore binária
Representada como vetor
Propriedade:
Árvore quase completa: preenchida da esquerda para a direita
Operações
Inserção (sift-up)
Adiciona no final e faz “subida” (heapify-up)
Remoção (sift-down)
Remove raiz e move último elemento para o topo
Realiza “descida” (heapify-down)
Heapify (Reorganização)
Constrói o heap a partir de vetor não ordenado em O(n)
Implementação
Heap é mais eficiente como vetor que como ponteiros
Índices no vetor:
Pai(i) = ⌊(i-1)/2⌋
Filho esquerdo(i) = 2i+1
Filho direito(i) = 2i+2
HeapSort
Etapas:
Constrói o Heap (O(n))
Troca raiz com último elemento
Reduz tamanho do heap e reaplica heapify
In-place (usa pouca memória extra)
Não estável
Complexidade
Pior caso, melhor caso, médio caso: O(n log n)
Heap Máximo: pai ≥ filhos
Heap Mínimo: pai ≤ filhos