Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM10 - Coggle Diagram
MM10
Heapsort
-
-
Como resultado, os elementos da matriz são eliminados em ordem decrescente
Mas como na implementação de um array de heap um elemento que está sendo excluído é colocado por último, o array resultante será examanete o array original classificado em ordem crescente
Heaps
É uma estrutura de dados inteligente e parcialmente ordenada, adequada para implementar filas prioritárias
Fila de prioridade: multiconjunto de itens com uma característica solicitável chamada prioridade de item, com as seguintes operações:
-
-
Encontrar um item com a prioridade mais alta (ou seja, o maior)
Um heap pode ser definido como árvore binária com chaves atribuídas aos seus nós, uma chave por nome, desde que as duas condições a seguir sejam atendidas:
1.Propriedade shape: a árvore binária está essencialmente completa ( ou simplesmente completa) , ou seja, todos os seus níveis estão cheios, exceto possivelmente o seu último nível, onde apenas algumas folhas mais à direita podem estar faltando
2.Dominância parental ou propriedade de heap: a chave em cada nó é maior ou igual às chaves de seus filhos (Está condição é considerada automaticamente satisfeita para todas as folhas)
Valores chaves de um heap são ordenados de cima para baixo, isto é, uma sequência de valores em qualquer caminho da raiz até uma folha é decrescente
No entanto, não há ordem da esquerda para direita nos valores chaves, ou seja, não há relação para nós do mesmo nível da árvore ou, mais geralmente, nas subárvores esquerda e direita do mesmo nó
Lista de importantes propriedades dos heaps, que não são difíceis de provar:
-
-
1. Existe exatamente uma árvore binária essencialmente completa com n nós, sua altura é igual a log2 n
4. Um heap pode ser implementado como um array gravando seus elementos de cima para baixo, da esquerda para a direita. É conveniente armazenar os elementos do heap nas posições 1 a n do array, deixando H[0] sem uso ou colocando ali uma sentinela cujo o valor é maior que todos do heap. Desta maneira:
a. As chaves do nó parental estarão nas primeiras n/2 posições do array, enquanto as chaves folhas ocuparão as últimas n/2.
b. Os filhos de uma chave na posição parental do array (1 <= i <= n/2) estarão nas posições 2i e 2i+1, e correspondentemente, o pai de uma chave na posição i (2 <= i <= n) estará na posição i/2
Assim, também poderíamos definir um heap como um array H[1...n] em que cada elemento i na primeira metade do array é maior ou igual aos elementos nas posições 2i e 2i+1
Heap bottom-up: algoritmo de construção, inicializa a árvore binária essencialmente completa com n nós, colocando as chaves na ordem dada e então “amontoa” a árvore como segue
Começando com o nó parental, o algoritmo verifica se a dominância do nó parental vale para a chave nesse nó. Caso contrário, o algoritmo troca a chave K do nó pela chave maior de seus filhos e verifica se a dominância parental é válida para K em sua nova posição. Este processo continua até que a dominância parental para K seja satisfeita
Depois de completar a “heapficação’ da subárvore enraizada no nó pai atual, o algoritmo prossegue fazendo o mesmo para o predecessor imediato do nó
-
Heap top-down: outro algoritmo de construção (menos eficiente), constrói um heap por meio de inserções sucessivas de uma nova chave em um heap previamente construído
3.Compare K com a chave do seu pai: se esta for igual ou maior que K, pare (a estrutura é um heap)
4.Caso contrário, troque as duas chaves e compare K com seu novo pai
2.Peneire K até o seu local apropriado na nova pilha, como segue
-
-
-
-