Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap e Heapsort - Coggle Diagram
Heap e Heapsort
Heapsort
-
Eficiência
-
Espaço: O(1) (in-place), o que significa que não precisa de memória extra significativa
Competitivo com Mergesort, mas geralmente mais lento que Quicksort para dados aleatórios na prática, apesar de ter uma garantia de pior caso melhor que Quicksort
O que são:
-
valor de cada nó pai é maior ou igual aos valores de seus filhos. Isso garante que o elemento de maior prioridade
ou menor prioridade esteja sempre na raiz.
Implementação
-
Construção de um Heap
Construção Bottom-Up
Começa com o array de entrada e, iterativamente, "heapifica" as subárvores, começando pelos últimos nós parentais e subindo até a raiz
Mais eficiente para construir um heap do zero, com complexidade de tempo O(n)
Construção Top-Down
Insere os elementos um a um em um heap inicialmente vazio, usando a operação de inserção.
Menos eficiente para construção inicial, com complexidade de tempo O(n logn)
Representação:
Embora seja uma árvore conceitualmente, a implementação mais eficiente é usando um array.
-
-