Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and Heapsort - Coggle Diagram

- - - - Algoritmo de construção de heap ascendente
    - - O algoritmo verifica se a dominância parental é valida para a chave neste nó
        
        Se não for o algoritmo troca a chave K do nó com a chave maior de seus filhos e verifica se a dominância parental é válida novamente
        
        Esse processo continua até que a dominância dos pais para K é satisfeita
    - - O algoritmo para depois que isso é feito na raiz da árvore
    - - Construído com 2n comparações
  - - - Anexa novo nó com chave K depois da ultima folha do heap
      - Faça K chegar ao seu lugar apropriado na pilha
        
        Compare K com a chave de seu pai
        
        Se for maior igual o algoritmo é interrompido
        
        A estrutura é uma pilha
        
        Caso não, troque as duas chaves e compare com seu novo pai
        
        Essa troca continua até que K não seja maior que seu pai ou até que atinja a raiz
      - A operação de inserção não pode exigir mais comparações de chaves do que a altura da pilha
        
        Fica ineficiente
        
        Altura
        
        logn na base 2
        
        Tempo de eficiência de inserção
        
        O(logn)
  - - - Se for verdadeiro
        
        ok
      - Se não
        
        Troca K com o maior de seus filhos
        
        Repete-se essa operação até a condição de dominância parental ser válida para K
    - - Determinada pelo número de comparações necessárias para "heapificar" a árvore após a troca
        
        Não pode exigir mais comparações do que o dobro da altura do heap
        
        Torna-se ineficiente
      - O(logn)
- - - - A propriedade da forma
        
        A árvore binária tem que ser completa
        
        Todos os níveis estão cheios, exceto o último nível
        
        Pode estar faltando folhas á direita
      - Propriedade Heap (Dominância Parental)
        
        A chave em cada nó é maior ou igual as chaves dos nós filhos
  - - - Não crescente
  - - - A altura é o chão de log n na base 2
- - - - Construa um heap para o array
    - - Aplicar a operação de exclusão de raízes n-1 vezes para a pilha restante
      - Elementos do array eliminados em ordem decrescente
      - Um elemento sendo excluído é colocado por último e o array resultante é exatamente a matriz ordenada em ordem crescente
  - - - Heapificação (Construção des heaps)
        
        O(n)
    - - Comparações C(n)
        
        Pertencem a classe O(nlogn)
    - - Pior caso e caso médio
    - - Um pouco mais lento do que o QuickSort mas compete com o MergeSort