Please enable JavaScript.

Coggle requires JavaScript to display documents.

M9 (Levitin) - Coggle Diagram

- - - - Heap
        
        Pode ser definido como um a árvore binária com "chaves" associadas aos nós (uma para cada nó), que possui duas propriedades fundamentais:
        
        1) Propriedade de formato: a árvore binária é essencialmente completa (ou simplesmente completa), isto é todos os seus níveis são necessariamente cheios com exceção do último, no qual pode haver ou não uma folha na extremidade direita da árvore.
        
        2) Dominância parental ou Propriedade heap: a chave em cada nó é sempre maior ou igual às chaves de seus filhos
        
        Uma versão alternativa, chamada min-heap, define que a chave em cada nó é sempre menor ou igual as chaves de seus filhos
        
        Não define qualquer tipo de relação obrigatória entre nós do mesmo nível. Dessa forma, filhos de um mesmo nó podem ser trocados de posição, sem que isso viole a integridade da heap
        
        Algumas importantes propriedades das heaps são:
        
        1) Existe exatamente uma árvore binaria essencialmente completa com n nós. Sua altura é igual a floor(log(n)_(2))
        
        2) A raiz de de uma heap sempre contém o maior elemento
        
        3) O conjunto formado por um nó da heap com todos os seus descendentes também define uma outra heap
        
        4) Uma heap pode ser implementada como uma array na qual a ordem em que os elementos são registrados da esquerda para a direita preserva a mesma ordem de cima para baixo em que os elementos da árvore binária estão dispostos
        
        É conveniente armazenar os elementos nas posições de 1 a n para facilitar os cálculos relativos às posições dos itens na array. A posição 0 normalmente é deixada vazia ou com uma "sentinela", isto é, um elemento maior que todos os demais que impede a substituição daquele espaço.
        Com essa convenção, duas propriedades se destacam:
        
        Os nós parentais (que não são folhas) estarão nas primeiras floor(n/2) posições da array, enquanto as folhas ocuparão as demais ceil(n/2) posições
        
        Os filhos de um nó parental na posição i (em que 1<= i <= floor(n/2) ) estarão nas posições 2i e 2i+1. De maneira reversa, o pai de uma folha na posição j estará na posição floor(j/2)
        
        Assim, é possível definir uma heap como a seguinte array:
        H[i] >= max{ H[2i], H[2i+1] } para i = 1, ... , floor(n/2)
        
        Existem duas principais maneiras de construir uma heap a partir de uma lista de chaves:
        
        Construção de baixo pra cima (bottom-up): Consiste em formar, inicialmente, um árvore binária contendo os elementos na ordem de entrada e em seguida "heapificando" a árvore
        
        O processo de heapficar é organizado da seguinte forma: Para cada nó parental, começando com o último (o mais à direita e próximo do nível inferior), é verificado se a dominância parental é respeitada, ou seja, se a chave do pai é maior que a de seus dois filhos. Em caso negativo, o filho com nó de maior valor troca de posição com seu pai, o qual é colocado numa nova posição em que a dominância parental é novamente verificada. O procedimento se repete até que a dominância seja respeitada, passando então para o próximo nó parental da heap (antecessor ao último que foi checado).
        O algoritmo se encerra após verificar todos as posições de nós parentais, ou seja, quando o último nó parental verificado tiver sido a raiz
        
        No pior caso, o número total de comparações para uma heap cheia com n elementos é:
        2(n - log(n+1)_(2))
        
        Construção de cima pra baixo (top-down): Consiste em inserir os elementos na heap, um a um, de maneira que a cada inserção a árvore é reorganizada para continuar sendo uma heap
        
        A inserção ocorre da seguinte forma: Inicialmente o nó é adicionado como uma folha após a última folha (à direita da última folha ou abaixo da primeira folha caso o último nível esteja cheio), sem alterar a posição dos demais nós. Em seguida, é comparado com seu pai e caso a dominância parental não seja respeitada, troca de lugar com esse pai. Na sua nova posição, a dominância parental é verificada novamente. Essa checagem continua até que a dominância seja satisfeita ou o nó se torne a raiz da árvore.
        
        Como o número comparações para a inserção não pode ser maior que a altura da heap com n nós, a qual vale em torno de log(n)_(2) , então a eficiência da inserção está em O(log(n))
        
        A remoção da raiz em heaps pode ser efetuada da seguinte forma:
        
        1 - Troca-se a chave da raiz com a última chave da heap
        
        2 - Diminui-se o tamanho da heap (ou seja, o último nó é "eliminado" do intervalo considerado como heap na array, embore ele continue sendo armazenado na array)
        
        3 - A árvore binária resultante é reorganizada através do método de heapficação descrito na construção bottom-up
        
        Como o número de comparações não pode ultrapassar o dobro da altura da heap, então a eficiência também está em O(log(n))
        
        É possível aplicar a estrutura de heap para construir um eficiente algoritmo de ordenação chamado:
        
        Heapsort
        
        É um algoritmo definido em dois estágios:
        
        1) Construção da heap a partir de uma dada array
        
        2) Remoção máxima: Aplicação da operação de remoção da raiz n-1 vezes
        
        Como na etapa 2 de cada remoção a raiz é posicionada no final da heap, que em seguida reduz seu tamanho em 1 unidade, as raízes vão sendo posicionadas da direita para a esquerda no final da array a medida que o intervalo considerado pela heap vai diminuindo. No entanto, como o valor da raíz é sempre o máximo da heap, os valores que são posicionadas da direita para a esquerda estão em ordem decrescente, o que, consequentemente, faz com que a array final fique disposta em ordem crescente
        
        A quantidade de comparações realizadas no segundo estágio está em O(n log(n)), sendo n o número de elementos da sequência a ser ordenada. Como o primeiro estágio está em O(log(n)) a eficiência final está em O(log(n)) + O(n log(n)) = O(n log(n))
        Uma análise mais meticulosa confirma que a eficiência do heapsort, tanto para o pior caso quanto para o caso médio, está em θ(n log(n))
        
        1 more item...
      - Filas de prioridade são multiconjuntos (conjuntos que podem conter elementos repetidos) de itens com uma característica ordenável chamada prioridade. Possui as seguintes operações:
        
        Encontrar um item com a maior prioridade
        
        Remover um item com a maior prioridade
        
        Adicionar um novo item ao multiconjunto