Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap - Coggle Diagram
Heap
Propriedades importantes
-
-
-
Se implementada em array, os primeiros elementos(1 ~ n/2) são os nós pais e os ultimos (n/2 ~ n) são as folhas. O pai de um nó sempre estará na posição i/2 (sendo i o indice do nó filho e o resultado é sempre arredonda para baixo)
Heapsort
Consiste em dois passos
-
2 - Remover a root (pelo algoritmo "Deletar a Root" falado nesse mapa mental na Heap->AlgoritmosImportantes) e armazená-la em um novo array
-
A eficiencia temporal do heapsort é big theta (n log n) e compete com o mergesort, mas é mais lento que o quicksort em casos médios
-
-
-
Algoritmos Importantes
Heapify
1 - Comparamos o ultimo elemento da heap com o seu pai para comprovar que o pai > filho, se for, há uma troca entre eles, caso não, não faz nada
2 - Continuamos indo por todas as folhas, depois nos nós completos até a root
OBS: caso haja uma mudança na heap (filho > pai), devemos analisar novamente esse nó, mas com o novo valor
-
Não é apenas uma pilha desordenada, a heap tem uma parcial ordenação dos seus membros. Mas a principal importancia da heap é o seu uso no Heapsort e implementar filas priorizadas