Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos - Coggle Diagram
Algoritmos
Heap
-
Uma árvore binária com chaves atribuídas seu nós, uma chave por nó, desde que as duas condições a seguir sejam atendidas:
A propriedade de forma - a árvore binária está essencialmente completa (ou simplesmente completa), ou seja, todos os seus níveis estão cheios, exceto possivelmente o último nível onde apenas algumas folhas mais à direita podem estar faltando.
Propriedades Importantes
Existe exatamente uma árvore binária essencialmente completa com n nós. Está
altura é igual a log2 n.
-
-
Um heap pode ser implementado como uma matriz registrando seus elementos de cima para baixo, da esquerda para a direita.
Em tal uma representação, uma. as chaves do nó parental estarão nas primeiras n / 2 posições da matriz, enquanto as teclas de folha ocuparão as últimas n / 2 posições.
Os filhos de uma chave na posição parental i da matriz i (1 ≤ i ≤ n / 2) irão estar nas posições 2i e 2i + 1, e, correspondentemente, o pai de uma chave na posição i (2 ≤ i ≤ n) estará na posição i / 2.
Enquanto as ideias por trás da maioria dos algoritmos que lidam com heaps são mais fáceis de entender, pensamos em heaps como árvores binárias, suas implementações reais são geralmente muito mais simples e eficiente com arrays.
O domínio parental ou propriedade de heap - a chave em cada nó é maior
que ou igual às chaves em seus filhos. (Esta condição é considerada automaticamente satisfeita para todas as folhas.)
-
-
-
Heapsort
-
Estágio 2 (exclusões máximas): Aplicar a operação de exclusão de raiz n - 1 vezes
para a pilha restante
-