Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap, oregon- HERE LIES MERGESORT HEST AT PEACE H.E.A.P.,…
Heap
Heapsort
-
-
-
Fazer a heap -> O n, tirar a raíz - 2n log2n
-
Mais devagar que Quicksort, velocidade parecida com Mergesort, mas não usa espaço extra
Propriedades
Existe uma árvore binária com n nós, cuja altura é floor(log2n)
-
-
Pode ser representada em array (parentes na primeira metade, folhas na outra / o filho de um nó na posição i vai estar nas posições 2i ou 2i+1, obs: posição 0 não é geralmente utilizada)
Caso uma das propriedades da heap não for satisfeito, uma troca entre o nó e o maior dos seus fihos é feita na próxima checagem (pode ser feito com menos de 2n comparações)
-
-
Inserção - novo elemento troca de lugar com os parentes até que seu pai seja maior ou esse elemento seja o nó (eficiência -> O logn)
Estrutura de data parcialmente ordenada, adequada para estabelecer ordens de prioridade
-
-
-
-
