CONCEITO DE ÁRVORE HEAPS
Por: Jociane Silva • 6/7/2018 • Resenha • 595 Palavras (3 Páginas) • 132 Visualizações
CONCEITO DE ÁRVORE HEAPS
São árvores binárias cujas chaves obedecem à seguinte propriedade:
- Os pais devem sempre ser maiores que os filhos (heap máximo).
- A árvore deve sempre estar completa, exceto pela última linha, na parte da direita.
Árvore binária completa ou quase completa:
- Min heap: Cada nó é menor que seus filhos
- Max heap: Cada nó é maior que seus filhos.
[pic 1]
Figura 1. © 2012 DI, PUC-Rio • Estruturas de Dados Avançadas.
Observações
• A estrutura de dados Heap não deve ser confundida com o Heap normalmente utilizado para designar a memória de alocação dinâmica.
• Não existe restrição para o número de filhos de um nó de uma árvore heap, porém o convencional são dois nós filhos.
Inserir um elemento
1. Insira o elemento no final do heap.
2. Compare ele com seu pai:
- Se estiver em ordem, a inserção terminou.
- Se não estiver, troque com o pai e repita o passo 2 até terminar ou chegar à raiz.
Exemplos de inserção:
[pic 2]
Figura 2. © 2012 DI, PUC-Rio • Estruturas de Dados Avançadas.
Remoção (do topo)
1. Coloque na raiz o último elemento
2. Compare ele com seus filhos:
- Se estiver em ordem, a remoção terminou.
- Se não estiver, troque com o maior filho e repita o passo 2 até terminar ou chegar numa folha.
Exemplos de inserção:
[pic 3]
Figura 3. © 2012 DI, PUC-Rio • Estruturas de Dados Avançadas.
APLICAÇÕES DE HEAPS
typedef struct _heap Heap;
Heap* heap_cria(int max);
void heap_insere(Heap* heap, float prioridade);
float heap_remove(Heap* heap);
struct _heap {
int max; /* tamanho maximo do heap */
int pos; /* proxima posicao disponivel no vetor */
float* prioridade; /* vetor das prioridades */
};
Heap* heap_cria(int max){
Heap* heap=(Heap*)malloc(sizeof(Heap));
heap->max=max;
heap->pos=0;
heap->prioridade=(float*)malloc(max*sizeof(float));
return heap;
}
INSERÇÃO:
void heap_insere(Heap* heap, float prioridade){
if ( heap->pos < heap->max ){
heap->prioridade[heap->pos]=prioridade;
corrige_acima(heap,heap->pos);
heap->pos++;
}
else printf("Heap CHEIO!\n"); }
static void troca(int a, int b, float* v) {
float f = v[a];
v[a] = v[b];
v[b] = f; }
static void corrige_acima(Heap* heap, int pos) {
while (pos > 0){
int pai = (pos-1)/2;
if (heap->prioridade[pai] < heap->prioridade[pos])
troca(pos,pai,heap->prioridade);
else {
break;
pos=pai;
}
}
REMOÇÃO:
float heap_remove(Heap* heap){
if (heap->pos>0) {
float topo=heap->prioridade[0];
heap->prioridade[0]=heap->prioridade[heap->pos-1];
...