Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps e HeapSort, Aplicações, Características, Tipos, Representação,…
Heaps e HeapSort
Aplicações
Fila de prioridade
HeapSort
Algoritmos em grafos (Dijkstra, Prim)
Características
HeapSort
Etapas
Trocar raiz com último
Reduzir tamanho do heap
Heapify na raiz
Construir max-heap
In-place
Não estável
Complexidade: O(n log n)
Tipos
HEAP
Definição
Árvore binária completa com propriedade de ordenação
Max-Heap (pai ≥ filhos)
Min-Heap (pai ≤ filhos)
Representação
Vetor (índices de pai e filhos)
Remoção
Operações em Heap
Inserção
Adiciona no fim e sobe (heapify-up)
Troca com último e desce (heapify-down)
Build Heap
Criação eficiente a partir de vetor (O(n))