Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps e Heapsort - Coggle Diagram

- - - - Por definição:
        Heap é um dicionário
        feito através de uma bst.
        Cada nó da árvore tem
        uma key associada a ela
        
        Deve seguir
        duas condições:
        
        Todos seus níveis
        devem estar cheios
        
        A chave de cada nó
        pai é igual ou maior
        que a chave de seus filhos
        
        Tem propriedades como:
        
        Altura = log2 n
        
        A Raíz contém o maior
        elemento
        
        Um nó com seus filhos é
        considerado uma heap
        
        Pode ser implementada por
        um array
        
        "Heapficação": Comparar
        os nós e trocá-los caso
        necessário para satisfazer
        a dominância parental
        
        Caso se exclua a raíz
        1º troca-se ela pelo menor
        elemento da árvore heapeficada
        e então heapfica novamente
        até satisfaer a dominância
        parental novamente
      - Fila de prioridade:
        multiconjunto de itens com
        uma característica ordenável
        ao que chamamos de
        prioridade de um item,
        
        Excluir o item com a alta prioridade
        
        Adicionar um novo item
        
        Pode encontrar um item com alta prioridade
- - - - Construção da heap pelo
        algoritmo é O(n) e sua eficiência
        de tempo tanto no pior e médio caso
        é n log n
        
        Não requer armazenamento
        extra
        
        Perde pro Quicksort,
        mas empata com o mergesort