Please enable JavaScript.
Coggle requires JavaScript to display documents.
HEAPS E HEAPSORT - Coggle Diagram
HEAPS E HEAPSORT
OPERAÇÕES BÁSICAS
INSERÇÃO - TOP DOWN
O(log n)
REMOÇÃO DO MAIOR
O(log n)
HEAPIFY(MAX-HEAP)
Complexidade depende da altura da subárvore.
Pior caso: O(log n)
Melhor caso: O(1)
CONSTRUÇÃO DO HEAP
TOP-DOWN
O(n log n)
BOTTOM-UP
O(n)
HEAPSORT
O(n log n)
CONCEITOS
DOIS TIPOS
Max-Heap - Pai ≥ filhos
Min-Heap- Pai ≤ filhos
USADO PARA
Fila de prioridade
Algoritmo de ordenação Heapsort
Algoritmos de grafos (Prim, Dijkstra)
PROPRIEDADES
FORMA
árvore binária completa (último nível da esquerda para a direita)
ORDEM