Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heap - Coggle Diagram

- - - - Dito isso, não há um requesito ou característica que determine a relação entre nódulos irmãos
        
        Por isso diz-se que a heap é parcialmente ordenada
      - Isso quer dizer que o caminho da raiz a uma folha vai sempre dar os valores em ordem decrescente (ou não crescente caso haja repetição)
- - - - O valor na raiz é o maior entre os nódulos
  - - - Na primeira metade das células, ficam os nódulos pais, na segunda, as folhas
        
        Os filhos de um nódulo na posição i estarão na posição 2 i e 2 i + 1
        
        Isto, é claro, para os nódulos com dois filhos. A definição de heap permite um único nódulo com apenas um filho. Para ela, há apenas o filho da posição 2 * i
    - - É possível montar uma heap a partir de uma lista de valores de duas formas
        
        Do fundo ao topo
        
        Primeiro, os valores são postos em uma árvore binária qualquer pela ordem que foram dados
        
        Depois, escolhe-se o pai de uma folha
        
        Verifica-se se algum dos filhos tem valor maior que o pai
        
        Se tiver, o valor do pai é trocado pelo maior valor entre os filhos
        
        1 more item...
        
        Do topo ao fundo
        
        Se trata de inserir um novo elemento a um heap já existente até que todos os valores da lista tenham sido incluidos
      - Inserção de Elementos
        
        Primeiro, cria-se uma nova folha com o valor a ser inserido
        
        Depois, compara-se o valor dessa folha ao de seu pai
        
        Se o valor do pai for maior ou igual, a inserção foi concluída. Se não, troca-se o pai e a folha
        
        Faz-se o mesmo com o novo pai
        
        O processo se repete até que o pai tenham valor maior ou igual ao inserido ou até que o valor inserido vire a nova raiz
        
        1 more item...
        
        Remoção de Elementos
        
        Para remover a raiz de uma heap...
        
        Troca-se de lugar a raiz com o último elemento da heap
        
        Remove-se efetivamente a raiz (diminuindo o tamanho da estrutura)
        
        Faz-se um processo de ordenação semelhante ao feito na construção da fundo-topo da heap
        
        1 more item...
        
        Heapsort
        
        O processo de remoção da raiz da heap torna a raiz, nódulo com o maior valor, uma folha
        
        Na implementação da heap como array, isso seria equivalente a mudar de lugar o maior item, o primeiro, com o menor
        
        Assim, esse processo feito de forma consecutiva, extrairia os elementos em ordem decrescente/não crescente
        
        1 more item...