Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps e Heapsort - Coggle Diagram
Heaps e Heapsort
-
Heapsort
-
-
-
Como resultado, os elementos do array são eliminados em ordem decrescente.
Sabe-se que o primeiro passo de construção está em O(n) e o segundo em O(n log n), então O(n) + O(n log n) = O(n log n)
Uma análise mais detalhada mostra que o heapsort está, de fato, em Θ(n log n) em ambos normal e pior casos.
Sendo assim, a eficiência do heapsort cai na mesma classe que o mergesort, só que, diferente do mergesort, o heapsort não precisa de espaço extra.
-
-
Filas prioritárias é um conjunto de itens com características ordenáveis chamadas de prioritárias, com as seguintes operações:
-
-
-
Um heap pode ser definido com uma árvore binária com chaves atribuídas aos seus nós, com uma chave por nó, previsto que as seguintes condições sejam atendidas:
1. A propriedade da forma: a árvore binária é essencialmente completa, ou seja, todos os seus níveis são cheios exceto possivelmente o último nível, onde somente algumas folhas à direita podem estar faltando.
2. A dominância parental ou propriedade heap: a chave de cada nó é maior ou igual às chaves dos seus respectivos filhos.
Heap é uma estrutura parcialmente ordenada de dados que implementa priority queues (filas prioritárias).
Podemos então definir heap como um array H[1...n] no qual todo elemento na posição i da primeira metade do array é maior ou igual aos elementos nas posições 2i e 2i+1.