Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps e Heapsort - Coggle Diagram

- - - - Heaps podem ser usadas para implementar filas de prioridade.
        
        Heap: árvore binária com chaves atribuídas aos seus nós, uma chave por nó, que possui duas condições:
        
        Condição do formato: é essencialmente completa. Todos os seus níveis estão completos, exceto, possivelmente, o último, onde algumas folhas mais à direita podem estar faltando;
        
        Dominação parental: a chave de cada nó é maior ou igual às chaves em seus filhos.
        
        Não existe relação entre os valores das chaves para nós do mesmo nível da árvore ou nas subárvores esquerda e direita do mesmo nó.
        
        Propriedades
        
        1- Existe exatamente uma árvore binária completa com n nós. Sua altura é floor(log de n na base 2);
        
        2- A raiz da heap sempre contém seu maior elemento;
        
        1 more item...
- - - - Temos a seguinte relação para o número de comparações necessárias para eliminar as chaves da raiz:
        C(n) <= 2n*(log de n na base 2)
        
        Logo, C(n) pertence a O(n*logn)
        
        A eficiência temporal é a mesma que o mergesort, porém heapsort não precisa de espaço extra.