Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps e HeapSort - Coggle Diagram
Heaps e HeapSort
Heaps: Estrutura de dados parcialmente ordenada, ótima para implementar fila de prioridade.
Ideia geral: Uma árvore binária, com um valor por nó. As seguintes condições devem ser seguidas:
- Shape property: A árvore binária deve ser completa, com a exceção possível do último nível, que pode ter as as folhas mais a direita faltando.
- Heap property: O valor armazenado em cada nó é maior ou igual que os valores armazenados em seus filhos (Folhas tem essa propriedade automaticamente validada).
Fila de prioridade: Uma lista de itens com uma característica ordenável 'prioridade'. Seus métodos são: Achar o item com a maior prioridade; Remover o item com a maior prioridade e adcionar um novo item.
-
Como construir um Heap?
-
-
Inserção:
- inserir o novo nó 'k' na posição após a última folha existente.
- "peneirar" 'k' para o seu devido lugar da seguinte forma: Comparar 'k' com o valor do pai. Se o pai tiver um valor maior, pare (a estrutura já é um heap). Senão, troque os dois nós e compare 'k' com seu novo pai. O processo continua até que 'k' não tenha mais um valor superior ao seu pai ou que ele chegue na raiz do heap.
Obs.: Como não é possível haver mais comparaçoes que a altura da árvore, a eficiência desse processo de inserção é O(log n)
Remoção
No caso especial do nó a ser removido ser a raiz:
- O valor na raiz troca de lugar com o valor 'k' da última folha.
- Diminui o tamanho da heap por 1.
- "Heapfy" a árvore, "peneirando para baixo" o valor de 'k' igual na tática de construção bottom-up até que 'k' mantenha a propriedade de dominância parental.
Obs.: Como esse processo não necessita de mais comparações que o dobro da altura da árvore, a eficiência é O(log n).
No caso de remoção de um nó qualquer:
- O valor no nó a ser deletado troca de lugar com o valor 'k' da última folha.
- Diminui o tamanho da heap por 1.
- "Heapfy" a árvore, de acordo: Se 'k' for maior que o valor de seu pai, "peneira para cima", igual na tática de construção bottom-up. Se 'k' for menor, "peneira para baixo".
HeapSort
Funciona em 2 etapas:
- Constrói o heap com o array passado como parâmetro.
- Realiza a operação de remover-raiz n-1 vezes, sucessivamente.
Eficiência:
Primeira etapa = O(n).
Segunda etapa = O(n log n).
Eficiência do HeapSort:
Cworst(n) = Cavg(n) = O(n log n).
Obs.: Experimentos apontam ser mais lento que quickSort, mas é capaz de competir com mergeSort.
É 'in-line', ou seja, não requer espaço adicional, opera direto no array a ser ordenado.