Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heap and Heapsort - Coggle Diagram

- - - - 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.
      - Existe exatamente uma árvore binária essencialmente completa com n nós. Sua altura é igual a floor(log2 n)
      - 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 do heap
      - Maximum Key Deletion from a heap:
        
        Etapa 2: Diminua o tamanho da heap em 1.
        
        Etapa 3: “Heapify” a árvore menor peneirando K para baixo da árvore exatamente da mesma maneira que fizemos no algoritmo de construção de heap ascendente. Ou seja, verifique a dominância dos pais para K: se for verdade, terminamos; se não, troque K com o maior de seus filhos e repita esta operação até que a condição de dominância parental seja válida para K em sua nova posição
        
        Efficiency : A eficiência da exclusão é determinada pelo número de comparações-chave necessárias para "heapify" a árvore após a troca ter sido feita e o tamanho da árvore ser diminuído em 1. Uma vez que isso não pode exigir mais comparações-chave do que duas vezes a altura do heap, o tempo a eficiência da exclusão também está em O (log n).
        
        Etapa 1: Troque a chave da raiz pela última chave K do heap