Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort - Coggle Diagram
Heaps and Heapsort
Heap
Não é uma pilha desordenada de itens como a palavra pode sugerir
Estrutura de Dados
Inteligente
Parcialmente Ordenada
Implementar Filas Prioritárias
Conjunto Multiplo de Itens
Prioridade de item
Operação
Encontrar um item de Maior Prioridade
Eliminar um item com maior Prioridade
Adicionar un item no Multiset
Útil
Implementado Eficientemente
Pedra Angular
Heapsort
Conceitos
Arvore Binaria
Chaves Atribuidas
Nós
Uma Chave por nó
Condição
Shape Property
Parental Dominance
Propriedades
Existe exatamente uma árvore binária completa com n nodes, em que sua altura é log2n
A raiz de um heap sempre contém seu maior elemento
O nó de um heap considerado com seus descendentes também é um heap
Uma pilha pode ser implementada como um array
Implementação
Arvore Binaria
Mais Eficiente
Técnicas de Construção
Bottom-Up heap Construction
Inicializa Árvore Binária completa com N nós
Coloca as chaves na ordem dada
Heapfies a arvore
Eficiência
Algoritmo pode ser rodado com menos de 2n comparações
Top-Down heap Construcion
Menos Eficiente
Inserir nova chave K
Inserir novo nó com a chave K
Após Ultima Folha do Heap
Colocar K até o lugar apropriado no heap
Comparar K com a chave de seu pai
Se for maior pare
Caso Contrário, troque as duas chaves
1 more item...
Heapsort
Algoritmo de Ordenamento
Estagio 1
Construir um Heap para um Conjunto
Resultado
Elementos da Matriz são eliminados em ordem decrescente
Matriz de heaps
Um elemento sendo eliminado é colocado por ultimo
Matriz resultante é igual a matriz original
1 more item...
Estagio 2
Apliar o root-deletion operation n-1 vezes para o heap