Heap e Fila de Prioridade

Links relacionados: DAS5102 Fundamentos da Estrutura da Informação

Conteúdo

• Teoria

Exemplo de Heap

heap.h

 1#ifndef HEAP_H_INCLUDED
 2#define HEAP_H_INCLUDED
 3
 4typedef struct heap Heap;
 5
 6Heap* heap_criar();
 7void heap_inserir(Heap* h, int e);
 8void heap_mostrar(Heap* h);
 9
10#endif // HEAP_H_INCLUDED

heap.c

 1#include "heap.h"
 2#include <stdio.h>
 3#include <stdlib.h>
 4
 5struct heap
 6{
 7	int ultimo;
 8	int tamanho;
 9	int *vet;
10};
11
12Heap* heap_criar()
13{
14	Heap *h = malloc(sizeof(Heap));
15	h->tamanho = 20;
16	h->ultimo = 0;
17	h->vet = malloc(h->tamanho * sizeof(int));
18	return h;
19}
20
21void heap_inserir(Heap* h, int e)
22{
23	h->ultimo++;
24	if (h->ultimo > h->tamanho)
25	{
26		h->vet = (int*) realloc(h->vet, h->tamanho * 2);
27		h->tamanho *= 2;
28	}
29	h->vet[h->ultimo] = e;
30
31	int k = h->ultimo;
32	while (((k / 2) > 0) && (h->vet[k] > h->vet[k / 2]))
33	{
34		int aux = h->vet[k];
35		h->vet[k] = h->vet[k / 2];
36		h->vet[k / 2] = aux;
37		k = k / 2;
38	}
39}
40
41void heap_mostrar(Heap* h)
42{
43	int i;
44	for (i = 1; i <= h->ultimo; i++)
45	{
46		printf("%3d", h->vet[i]);
47	}
48	printf("\n");
49}

main.c

 1#include <stdio.h>
 2#include <stdlib.h>
 3#include "heap.h"
 4
 5int main()
 6{
 7	Heap* h = heap_criar();
 8	heap_inserir(h, 17);
 9	heap_inserir(h, 15);
10	heap_inserir(h, 12);
11	heap_inserir(h, 9);
12	heap_inserir(h, 10);
13	heap_inserir(h, 4);
14	heap_inserir(h, 1);
15	heap_inserir(h, 7);
16	heap_inserir(h, 3);
17	heap_inserir(h, 6);
18	heap_mostrar(h);
19	heap_inserir(h, 16);
20	heap_mostrar(h);
21	heap_inserir(h, 4);
22	heap_mostrar(h);
23	return 0;
24}

Roteiro

Objetivos

• Exercitar a criação de heaps usando arrays como estrutura base para armazenamento das informações;
• Utilizar a heap como estrutura base para a implementação de uma fila de prioridade.

Exercício 1

Crie uma TAD max_heap:

• Utilize um array como estrutura de dados base para o armazenamento das chaves de prioridade;

• Defina a estrutura de dados necessária (Dica: crie uma struct contendo o array e outras variáveis necessárias, tal como o último elemento);

• Crie uma função que inclua um novo elemento na heap;
• Crie uma função que remova o elemento de mais alta chave na heap;

Exercício 2

Abaixo é apresentado um exemplo esquemático para a inserção de um novo elemento na heap binária. Crie um exemplo à semelhança do dado para a remoção do elemento com maior chave;

Exercício 3

Os exercícios 1 e 2 lidaram com a max_heap. O que seria necessário mudar na TAD acima para implementarmos uma min_heap?