Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap and Heapsort - Coggle Diagram
Heap and Heapsort
Heap
A estrutura de dados chamada "heap" definitivamente não é uma pilha desordenada de itens como a definição da palavra em um dicionário padrão pode sugerir. Em vez disso, é uma estrutura de dados inteligente e parcialmente ordenada, especialmente adequada para a implementação de filas de prioridade. Lembre-se de que uma fila de prioridade é um multiconjunto de itens com uma característica que pode ser solicitada, chamada de prioridade de um item:
-Achar um item com a prioridade mais alta.
-Deletar um item com a prioridade mais alta.
-Adicionar um novo item ao multiset
É principalmente uma implementação eficiente dessas operações que torna o heap interessante e útil. As filas de prioridade surgem naturalmente em aplicações como o agendamento de execuções de tarefas por sistemas operacionais de computador e gerenciamento de tráfego por rede de comunicação. O heap é também a estrutura de dados que serve como base de um algoritmo de classificação teoricamente importante chamado heapsort
Definição
Um heap pode ser definido como uma árvore binária com chaves atribuídas a seus nós, uma chave por nó, desde que as duas condições a seguir sejam atendidas:
1- A propriedade de forma - a árvore binária está essencialmente completa (ou simplesmente completa), ou seja, todos os seus níveis estão cheios, exceto possivelmente o último nível, onde apenas algumas folhas à direita podem estar faltando
2- A dominância parental ou propriedade de heap - a chave em cada nó é maior ou igual às chaves em seus filhos.
Importantes propriedades
- Existe exatamente uma árvore binária essencialmente completa com n nós. Sua altura é igual a log2 n.
- A raiz de um heap sempre contém seu maior elemento.
- Um nó de um heap considerado com todos os seus descendentes também é um heap.
- Um heap pode ser implementado como um array registrando seus elementos de cima para baixo, da esquerda para a direita. É conveniente armazenar os elementos do heap nas posições 1 a n de tal matriz, deixando H [0] sem uso ou colocando lá uma sentinela cujo valor é maior do que todos os elementos no heap.
Construção
Bottom up
Ele inicializa a árvore binária essencialmente completa com n nós colocando as chaves na ordem dada e então “heapifica” a árvore como segue. Começando com o último nó parental, o algoritmo verifica se a dominância parental é válida para a chave neste nó. Caso contrário, o algoritmo troca a chave do nó K com a chave maior de seus filhos e verifica se a dominância dos pais é válida para K em sua nova posição. Este processo continua até que a dominância dos pais para K seja satisfeita. (Eventualmente, ele tem que fazer porque ele vale automaticamente para qualquer chave em uma folha.) Depois de completar a "heapificação" da subárvore enraizada no nó parental atual, o algoritmo continua a fazer o mesmo para o predecessor imediato do nó. O algoritmo para depois que isso é feito para a raiz da árvore
Top down
O algoritmo alternativo (e menos eficiente) constrói um heap por inserções sucessivas de uma nova chave em um heap construído anteriormente. Obviamente, essa operação de inserção não pode exigir mais comparações de chave do que a altura do heap. Como a altura de um heap com n nós é cerca de log2 n, a eficiência de tempo de inserção é O (log n). A deleção também tem a mesma eficiência
Heapsort
É uma algoritmo de ordenação que funciona em duas etapas:
1- Contrução do heap para um dado array
2- Exclusões máximas: Aplicar a operação de exclusão de raiz n - 1 vezes para a pilha restante.
Eficiência
Uma análise mais detalhada mostra que a eficiência de tempo do heapsort é, de fato, em Theta (n log n) nos piores casos e no médio. Assim, a eficiência de tempo do heapsort cai na mesma classe que a do mergesort. Ao contrário do último, o heapsort não requer nenhum armazenamento extra. Os experimentos de tempo em arquivos aleatórios mostram que o heapsort é executado mais lentamente do que o quicksort, mas pode competir com o mergesort
Como resultado, os elementos da matriz são eliminados em ordem decrescente. Mas, como na implementação do array de heaps, um elemento que está sendo excluído é colocado por último, o array resultante será exatamente o array original classificado em ordem crescente.