Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and Heapsort - Coggle Diagram

- - - - O formato da árvore: todos os níveis da árvore binária estão lotados, a exceção pode ser feita para a folhas mais a direita.
      - Dominância parental / heap property: A chave de cada nó é maior ou igual para as chaves de seus filhos (Condição tem que satisfazer em todos os níveis)
      - Podemos definir também um heap como um array H[1..n] em que todos os elementos na posição i na primeira metade do array são maiores ou iguais para os elementos nas posições 2i e 2i + 1
  - - - É conveniente armazenar os elementos do heap na posição 1 a n de cada um array, deixando o H[0] sem uso ou colocando um sentinela lá o qual seu valor seja maior do que todos os elementos no heap.
        
        A chave de nó parental deverá ser o primeiro [n/2] posições no array, enquanto a chave da folha ocupará as últimas [n/2] posições.
        
        Os filhos de uma chave na posição parental de um array i ( 1 <= i <= n/2) estarão na posição 2i e 2i + 1, e, de modo correspondente, o parente de uma chave na posição i ( 2 <= i <= n) estará na posição ([ i / 2])
  - - - Bottom-up heap construction
        
        Inicializa a árvores binárias tem que ser essêncialmente completas com n nós pelo lugares das keys dado na ordem dada pelos "heapifies"
        
        Começando com o último parente do nó, o algoritmo checa se o parente dominante segura por chaves neste nó. Caso nãp, o algoritmo muda de nó de chave com uma chave mauiior de um outro filho e checa se a dominância for K na nova posição.
        
        Estrutura do algoritmo
        
        HeapBottomUp(H[1..n])
        // Constructs a heap from elements of a given array
        // By the bottom-up algorithm
        // Input: An array H[1..n] of orderable items
        // Output: A heap H[1..n]
        for i <- [n / 2] downto 1 do
        k <- i; v <- H[k]
        heap <- false
        while not heap and 2 k <= n do
        j <- 2k
        if j < n // there are two children
        if H[j] < H[j+1] j <- j + 1
        if v >= H[j]
        heap <- true
        else H[k] <- H[j]; k <- j
        H[k] <- v
        
        Questão de eficiência no pior caso?
        
        1 more item...
      - Top-down heap construction
        
        É uma alternativa menos eficiente
        
        Como podemos inserir uma nova chave dentro de um heap?
        
        Primeiro anexamoso novo nó com a chave K e depois na última folha da de existência do heap. Em seguida guie K até seu lugar apropriado no novo heap.
        
        Compare K com suas chaves parentais, caso for último for maior ou igual a K, pare. Caso não, troque essas duas chaves e compare K com o novo parente, tal troca continua até encontrar o ultimo parente ou a raiz.
        
        A inserção não pode requerer mais comparações de chaves do que a altura da heap.
        
        A eficiência da inserção é BIG OH( log n)
  - - - Pode ser feito pelo seguinte algoritmo: Maximum Key Deletion
        
        Step 01: Mudar a chave da raiz com a última chave K de um heap
        
        Step 02: Decrementar o tamanho da heap por 1
        
        Step 03: Verificaremos a dominância parental por K, se segurar, nós fazemos, caso não, trocamos K com um filho maior e repetimos a operação até a condição parental for satisfeita
- - - - É um conjunto multiplo de itens com uma ordem característica chamada de prioridade de um item.
        
        Podemos encontrar um elemento com a maior prioridade
        
        Deletar o item com a maior prioridade.
        
        Adicionar um item no conjunto
- - - - Stage 01: (heap constructuin) Contruir uma heap por um array dado
      - Stage 02: (maximum deletions)Aplicar a root-deletion operação n - 1 vezes para reimaginar heap
      - Como resultado, os elementos do array são eliminados e sua ordem decrementa. Mas, desde que o array implementado de heap um elemento começado a ser deletado no último lugar, o resultado será um array exatamente do array original ordenado e incrementado na ordem.
        
        O estágio de construção da heap será da ordem BIG OH (n)
        
        A eficiência do heapsort é da grandeza do BIG THETA (n log n) no médio e pior caso
        
        Não requer armazenamento extra
        
        Experimentos mostram que é mais lento que um quicksort, mas pode ser competitivo com o mergesort