Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heap - Coggle Diagram

- - - - A raiz contém o maior elemento
      - A posição da raiz no array começa a partir de 1
      - Altura = função piso (log2 n)
      - Todos os nós pais(internos) são alocados nas primeiras posições do array pela função piso(n/2)
      - Todos os nós folhas ocupam as ultimas posições pela função teto(n/2)
      - Construção
        
        Bottom-up
        
        Elementos inseridos de uma vez
        
        Utilizamos a função Heapify para verificar todos os nós internos do último ao primeiro
        
        Sabemos os elementos
        
        Top-down
        
        Inserimos cada elemento por vez
        
        A cada inserção verificamos as condições do heap através de uma função chamada Heapify
        
        Não sabemos os elementos
        
        Operação
        
        Remoção da raiz
        
        Trocamos de a raiz de lugar com a último nó do heap e diminuímos seu tamanho por 1 e utilizamos a função Heapify para ordenarmos o heap novamente
        
        Heapsort
        
        Algoritmo de ordenação
        
        1º Etapa: Constrói um heap de um certo array pela abordagem do bottom-up
        
        2º Etapa: Aplica a operação de remoção da raiz para ordenar o array
        
        Eficiência temporal
        
        bottom-up em O(n)
        
        Remoção em O(log n)
        
        O(n) + O(n log n) = O(n log n)