Skip to content

Fila de Prioridade e Heap

Uma fila de prioridade é uma estrutura de dados com duas operações básicas:

  • Inserir um novo elemento
  • Remover o elemento com maior chave (prioridade)

Pilhas e filas assemelham-se às filas de prioridade, na primeira o elemento de maior prioridade é o último inserido, e nas filas o contrário acontece.

Implementação

header.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef struct
{
    char nome[20];
    int chave;
} Item;

typedef struct
{
    Item *v;
    int n, tamanho;
} FP;
typedef FP *p_fp;

p_fp criar(int tam);
void inserir(p_fp fila, Item item);
Item extrair_maximo(p_fp fila);
int vazia(p_fp fila);
int cheia(p_fp fila);

void troca(Item *a, Item *b)
{
    Item t = *a;
    *a = *b;
    *b = t;
}

A troca de elementos será frequente, então para facilitar a leitura do código, foi implementada a função troca.

Criação da fila prioridade

A criação da fila de prioridade consiste basicamente em alocar memória para as estruturas e definir o tamanho com e quantidade de valores preenchidos.

criar.c
1
2
3
4
5
6
7
8
p_fp criar(int tam)
{
    p_fp fila = malloc(sizeof(FP));
    fila->tamanho = tam;
    fila->v = malloc(sizeof(Item) * tam);
    fila->n = 0;
    return fila;
}

Inserção

A inserção é simples e feita no final do vetor.

inserir.c
1
2
3
4
void inserir(p_fp fila, Item item)
{
    fila->v[fila->n++] = item;
}

A complexidade do algoritmo é \(O(1)\).

Remoção do máximo

O algoritmo percorre o vetor, guardando o índice do maior valor encontrado até o momento. No final, é feita a troca do último elemento do vetor fprio->v[fprio->n-1] com o maior valor encontrado fprio->v[max]. Então, o valor de n é decrementado, pois um item foi removido, e o valor removido é retornado.

extrair_maximo.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Item extrair_maximo(p_fp fila)
{

    int index = 0;
    for (int i = 0; i < fila->n; i++)
        if (fila->v[i].chave > fila->v[index].chave)

            index = i;

    troca(&fila->v[index], &fila->v[fila->n - 1]);
    fila->n--;
    return fila->v[fila->n];
}

A complexidade da extração do máximo é \(O(n)\).

Os custos das operações inserção e extração são invertidas caso se deseje manter o vetor ordenado.

Cheia vs Vazia

Para verificar se a fila está cheia, ou vazia, podemos usar as funções a seguir.

vazia.c
1
2
3
4
int vazia(p_fp fila)
{
    return fila->n == 0;
}
cheia.c
1
2
3
4
int cheia(p_fp fila)
{
    return fila->tamanho - fila->n == 0;
}

Heap

Definição

O heap de máximo é uma árvore em que os filhos de cada nó são menores ou iguais ao pai. Simetricamente, no heap de mínimo os filhos são maiores ou iguais ao pai. Essa estrutura possui a propriedade de alocar o maior (ou menor) elemento na raiz da árvore.

Um heap não é uma árvore binária de busca, nele os dados estão bem menos estruturados, pois o interesse está apenas em encontrar o maior (ou menor) valor.

Figura 1: Heap de Máximo. Fonte: [1]

Implementação

O Heap pode ser representado na forma de arvore binária completa, utilizando vetores.

heap.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void insere_no_heap(p_fp fila, Item item);
Item get_maximo_heap(p_fp fila);
void altera_prioridade(p_fp fila, int posicao, int novo_valor);

// Operações

void sobe_no_heap(p_fp fila, int k);
void desce_no_heap(p_fp fila, int k);

#define PAI(i) ((i - 1) / 2)
#define F_ESQ(i) (2 * i + 1)
#define F_DIR(i) (2 * i + 2)

Subindo e Descendo no Heap

sobenoheap.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Sobe um elemento das folhas em direção a raiz, de forma que
//       os filhos de um nó sejam sempre menores que ele.
void sobe_no_heap(p_fp fila, int k)
{

    if (k > 0 && fila->v[k].chave > fila->v[PAI(k)].chave)
    {
        troca(&fila->v[k], &fila->v[PAI(k)]);
        sobe_no_heap(fila, PAI(k));
    }
}
descenoheap.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void desce_no_heap(p_fp fila, int k)
{
    if (k < 0 || F_ESQ(k) >= fila->n || F_DIR(k) >= fila->n)
        return;
    Item f_esq, f_dir;
    int maior_filho;
    f_esq = fila->v[F_ESQ(k)];
    f_dir = fila->v[F_DIR(k)];

    if (fila->v[k].chave >= f_esq.chave && fila->v[k].chave >= f_dir.chave)
        return;
    else
    {
        maior_filho = (f_esq.chave >= f_dir.chave) ? F_ESQ(k) : F_DIR(k);

        troca(&fila->v[k], &fila->v[maior_filho]);
        desce_no_heap(fila, maior_filho);
    }
}

Inserção

heap.c
1
2
3
4
5
6
7
8
void insere_no_heap(p_fp fila, Item item)
{
    if (fila->n <= fila->tamanho)
    {
        fila->v[fila->n++] = item;
        sobe_no_heap(fila, fila->n - 1);
    }
}

A inserção custa \(O(log\ n)\), pois subimos no máximo até a raiz.

Extraindo o máximo

getmaximoheap.c
1
2
3
4
5
6
7
8
9
// Trocamos o maior elemento v[0] com o último inserido[n-1] e ajustamos o heap.
Item get_maximo_heap(p_fp fila)
{
    Item max = fila->v[0];
    troca(&fila->v[0], &fila->v[fila->n - 1]);
    fila->n--;
    desce_no_heap(fila, 0);
    return max;
}

Extrair o valor máximo custa \(O(log\ n)\), pois descemos no máximo a altura da árvore.

Mudando a prioridade

Se a prioridade do item aumentar, precisamos subir arrumando, caso contrário, descer arrumando.

alteraprioridade.c
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void altera_prioridade(p_fp fila, int posicao, int novovalor)
{
    int old_prior = fila->v[posicao].chave;

    fila->v[posicao].chave = novovalor;

    if (novovalor >= old_prior)
        sobe_no_heap(fila, posicao);
    else
        desce_no_heap(fila, posicao);
}

Para alterar a prioridade precisamos saber a posição do item no heap, e a busca por essa posição tem custo \(O(n)\). Podemos melhorar esse custo incluindo um campo id com valores de 0 a n-1 nos itens, criando um vetor de n posições como parte do heap armazenando a posição de cada item no heap, então podemos recuperar essa posição em \(O(1)\).

Referências

[1] Fila de Prioridade e Heap - Notas de aula do professor Rafael C. S. Schouery, disponíveis no link.