Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heap e heapsort - Coggle Diagram
Heap e heapsort
Prioridades
Busca de item de maior prioridade
Apagando um item de maior prioridade
Adicionando um item em múltiplas inserções
Heap
Definida por uma árvore binária com chaves atribuídas aos nós, uma chave por nó
Prioridade de forma
Essencialmente completa
Dominância parental
Lista de propriedades importantes
Existe exatamente uma árvore binária completa com n nós de tamanho igual a log2 n
A raiz da heap sempre contém o maior elemento
O nó da heap considera que todos os seus descendentes também são heaps
Uma heap pode ser implementada por um vetor gravando os elementos de cima para baixo e esquerda pra a direita
É conveniente que armazene na heap o elemento na posição 1 de n deste vetor, exceto H(0) que está o sentinela
Construção de baixo para cima
Começa pelo último nó parental
Eficiência
Pior caso
2(n - log2 n(n+1))
Construção de cima para baixo
Inserções sucessivas de chaves
Eficiência
Θ(log n)
Apagando uma chave arbitrária
Troca as posições da chave da raiz com a última chave da heap
Diminui o tamanho da heap em 1
Heapsort
Implementa o algoritmo de sorteio
Constrói a heap
Implementa apagar a raiz em n-1
Elementos são apagados em forma decrescente
Θ(nlog n)
Pior caso
Caso médio
Θ(n)
Fila de prioridades