Fila de prioridade

Em uma fila comum, sai primeiro quem chegou primeiro. Em muitas situações, porém, a ordem de chegada não é o que importa. No pronto-socorro, é atendido antes o paciente em estado mais grave. No sistema operacional, roda antes o processo mais urgente. Uma fila de prioridade é a estrutura para essas situações: cada elemento tem uma prioridade, e quem sai é sempre o elemento de maior prioridade.

Filas de prioridade aparecem em muitos algoritmos importantes: no escalonamento de processos, nos algoritmos de Dijkstra (caminhos mínimos) e de Prim (árvore geradora mínima), no algoritmo de Huffman (compressão de dados), em simulações de eventos (processados na ordem em que acontecem) e em buscas em inteligência artificial, como o algoritmo A*.

O TAD fila de prioridade

As operações do nosso TAD são:

Para manter o foco na estrutura, o elemento é um inteiro, e a sua prioridade é o próprio valor: quanto maior o número, maior a prioridade. Mais adiante, há um exemplo com registros, em que cada elemento guarda uma prioridade e outros dados.

Implementações elementares

Não é difícil imaginar formas de implementar uma fila de prioridade. O problema é que, nas mais óbvias, algumas operações ficam rápidas e outras ficam lentas.

• Vetor desordenado. Cada elemento entra no fim do vetor, em . Para encontrar (ou remover) o maior, é preciso percorrer o vetor inteiro, em .
• Lista encadeada desordenada. A mesma ideia, com uma lista: inserir no início custa , e encontrar o maior, .
• Vetor ordenado. O maior fica sempre na última posição, e consultá-lo ou removê-lo custa . Em compensação, inserir exige encontrar a posição certa e deslocar os elementos maiores, em .
• Lista encadeada ordenada. Com a lista em ordem decrescente, o maior é o primeiro, em . Inserir exige percorrer a lista até a posição certa, em .
• Árvore binária de busca. O maior é o nó mais à direita, e inserir, remover e consultar custam : em média, para inserções em ordem aleatória, mas no pior caso.
• Árvore de busca balanceada (AVL ou LLRB). As três operações custam no pior caso.

A árvore balanceada resolve o problema, mas é uma estrutura pesada para uma tarefa simples: ela mantém todos os elementos em ordem, enquanto a fila de prioridade só precisa saber, a cada momento, qual é o maior. O heap binário aproveita exatamente essa folga.

Heap binário

Pela propriedade de ordem, a prioridade nunca aumenta ao descer pela árvore. Então o maior elemento está sempre na raiz. Um heap mínimo (ou min-heap) é o mesmo, com a ordem invertida: todo nó tem prioridade menor ou igual à dos filhos, e o menor elemento fica na raiz.

Repare que o heap não é uma estrutura ordenada. A propriedade de ordem compara cada nó só com os seus filhos: nada diz sobre irmãos, nem sobre nós de subárvores diferentes. A única garantia é que, em qualquer caminho da raiz até uma folha, as prioridades não aumentam.

O heap guardado em um vetor

Como a árvore é completa, ela pode ser guardada em um vetor, sem ponteiros: os nós são numerados nível por nível, da esquerda para a direita, começando em 1, e o nó de número fica na posição do vetor. A forma completa garante que não sobram buracos.

Com essa numeração, o parentesco vira aritmética: para o nó na posição ,

• o pai está na posição (a raiz, na posição 1, não tem pai).
• o filho esquerdo está na posição , se .
• o filho direito está na posição , se .

Em termos do vetor, é um heap máximo se para todo de 2 a . A posição 0 não é usada, o que deixa as contas mais simples (com o vetor começando em 0, o pai de seria e os filhos, e ).

Como a árvore é completa, a sua altura é . Todas as operações a seguir percorrem, no máximo, um caminho da raiz até uma folha, e por isso custam .

A estrutura em C

struct filaPrioridade {
    int *A;             /* heap em A[1..tamanho]; A[0] não é usado */
    int capacidade;     /* número máximo de elementos */
    int tamanho;        /* número atual de elementos */
};

FilaPrioridade *criaFP(int capacidade) {
    FilaPrioridade *fp = malloc(sizeof(FilaPrioridade));
    fp->A = malloc((capacidade + 1) * sizeof(int));    /* posições 0 a capacidade */
    fp->capacidade = capacidade;
    fp->tamanho = 0;
    return fp;
}

Corrigindo a propriedade de heap

Todas as operações que alteram o heap (inserir, remover, alterar uma prioridade) têm algo em comum: depois da alteração, a propriedade de ordem pode estar violada em uma única posição. Duas funções auxiliares restauram a propriedade nessa situação, e são a base de toda a implementação.

Subindo

corrigeSubindo(fp, i) supõe que já é um heap e que só pode estar fora do lugar, maior que o pai.

1. 1

   Compare com o pai#

   Se é a raiz, ou se não é maior que o pai, , não há nada a corrigir.

2. 2

   Troque e suba#

   Senão, troque com o pai. A propriedade passa a valer entre os dois, mas o elemento, agora uma posição acima, pode ser maior que o novo pai: repita a partir da posição do pai.

/* A[1..i-1] já é heap: sobe A[i] até o lugar dele */
static void corrigeSubindo(FilaPrioridade *fp, int i) {
    int pai = i / 2;
    if (i >= 2 && fp->A[i] > fp->A[pai]) {
        troca(&fp->A[i], &fp->A[pai]);
        corrigeSubindo(fp, pai);
    }
}

O elemento sobe por um único caminho em direção à raiz, então a função faz no máximo trocas: .

Descendo

corrigeDescendo(fp, i) supõe que as subárvores com raízes e já são heaps e que só pode estar fora do lugar, menor que algum filho.

1. 1

   Encontre o maior dos três#

   Entre e os filhos que existirem, encontre o maior. A comparação de cada filho é feita com o maior encontrado até ali, e não com .

2. 2

   Pare ou troque#

   Se o maior é o próprio , a propriedade vale e não há nada a fazer. Senão, troque com o maior filho.

3. 3

   Desça#

   O elemento, agora na posição do filho, pode ser menor que algum dos novos filhos: repita a partir daquela posição.

/* As subárvores de 2i e 2i + 1 já são heaps: desce A[i] até o lugar dele */
static void corrigeDescendo(FilaPrioridade *fp, int i) {
    int maior = i;
    int l = 2 * i;
    int r = 2 * i + 1;
    if (l <= fp->tamanho && fp->A[l] > fp->A[maior])
        maior = l;
    if (r <= fp->tamanho && fp->A[r] > fp->A[maior])
        maior = r;
    if (maior != i) {
        troca(&fp->A[i], &fp->A[maior]);
        corrigeDescendo(fp, maior);
    }
}

É preciso trocar com o maior filho: ele sobe e passa a ser pai do outro, e só o maior dos dois pode ser pai do outro sem violar a ordem. Como em corrigeSubindo, o elemento percorre um único caminho, agora em direção às folhas, e o custo é .

Inserção

O novo elemento entra na primeira posição livre, , o que mantém a árvore completa. A ordem pode ser violada apenas ali, entre o novo elemento e o pai, e corrigeSubindo resolve.

bool insereFP(FilaPrioridade *fp, int x) {
    if (fp->tamanho == fp->capacidade)
        return false;                   /* fila cheia */
    fp->tamanho++;
    fp->A[fp->tamanho] = x;             /* primeira posição livre */
    corrigeSubindo(fp, fp->tamanho);
    return true;
}

A inserção custa , o custo de corrigeSubindo.

bool insereFP(FilaPrioridade *fp, int x) {
    if (fp->tamanho == fp->capacidade)
        return false;
    int i = ++fp->tamanho;
    while (i > 1 && x > fp->A[i / 2]) {
        fp->A[i] = fp->A[i / 2];    /* o pai desce */
        i = i / 2;                  /* o buraco sobe */
    }
    fp->A[i] = x;
    return true;
}

Remoção do máximo

O maior elemento está na raiz, . Para removê-lo sem deixar um buraco no topo da árvore, ele troca de lugar com o último elemento, , e o tamanho diminui. A árvore continua completa, e as subárvores das posições 2 e 3 continuam sendo heaps. Só a raiz pode estar fora do lugar, e corrigeDescendo resolve.

int removeMaxFP(FilaPrioridade *fp) {
    int x = fp->A[1];                   /* o maior está na raiz */
    troca(&fp->A[1], &fp->A[fp->tamanho]);
    fp->tamanho--;
    corrigeDescendo(fp, 1);
    return x;
}

int maximoFP(const FilaPrioridade *fp) {
    return fp->A[1];
}

A remoção custa , e a consulta ao máximo, . As duas funções supõem que a fila não está vazia: quem as chama deve testar antes com vaziaFP. Com a fila vazia, não há elemento a devolver, e é lixo.

Alteração de prioridade

Alterar a prioridade de um elemento viola a ordem, no máximo, na posição dele. Se a prioridade aumentou, ele pode ter ficado maior que o pai, e precisa subir. Se diminuiu, pode ter ficado menor que um filho, e precisa descer.

void alteraFP(FilaPrioridade *fp, int i, int k) {
    if (i < 1 || i > fp->tamanho)
        return;
    int antigo = fp->A[i];
    fp->A[i] = k;
    if (k > antigo)
        corrigeSubindo(fp, i);          /* pode estar em conflito com o pai */
    else if (k < antigo)
        corrigeDescendo(fp, i);         /* pode estar em conflito com um filho */
}

Só uma das duas correções é executada, então o custo é .

Essa versão tem uma limitação importante: ela recebe a posição do elemento no vetor, e quem usa a fila normalmente não sabe essa posição, que muda a cada troca. Para alterar a prioridade de um elemento identificado de outra forma (o vértice 5, a tarefa "backup"), a fila precisa guardar onde cada elemento está. É o segundo exercício desta página, e é assim que Dijkstra e Prim usam a fila de prioridade, com uma operação que só aumenta (ou, na fila mínima, só diminui) a prioridade, chamada de increase key (ou decrease key).

Construção a partir de um vetor

Às vezes, todos os elementos já estão disponíveis em um vetor, e queremos transformá-lo em um heap. Inserir um a um custa . Há uma forma melhor: aplicar corrigeDescendo a cada posição, de baixo para cima.

As posições de a são folhas, e cada folha já é um heap de um elemento. Então começamos em , a última posição com filhos, e vamos até a raiz. Quando chega a vez da posição , as subárvores de e já foram corrigidas, que é exatamente o que corrigeDescendo supõe.

static void constroiHeap(FilaPrioridade *fp) {
    for (int i = fp->tamanho / 2; i >= 1; i--)
        corrigeDescendo(fp, i);
}

FilaPrioridade *constroiFP(const int *v, int n, int capacidade) {
    FilaPrioridade *fp = criaFP(capacidade < n ? n : capacidade);
    for (int i = 0; i < n; i++)
        fp->A[i + 1] = v[i];
    fp->tamanho = n;
    constroiHeap(fp);
    return fp;
}

A ordem do laço é essencial: de cima para baixo, uma posição seria corrigida antes das suas subárvores, e o resultado poderia não ser um heap (é o Programa 2).

Uma conta rápida diz que a construção custa : são chamadas de corrigeDescendo, cada uma . Mas esse limite não é justo. A maioria dos nós está perto das folhas, onde corrigeDescendo desce pouco, e só os poucos nós perto da raiz podem descer muito. Uma análise mais cuidadosa mostra que a construção custa, na verdade, .

O TAD completo

O programa abaixo usa o TAD completo. Ele insere dez valores, insere o 15 (a inserção da figura), remove o máximo, altera uma prioridade e esvazia a fila, imprimindo o vetor depois de cada passo. No fim, constrói um heap a partir dos mesmos dez valores com constroiFP.

Elementos com dados

Em uma aplicação real, cada elemento traz, além da prioridade, os dados que interessam: o nome da tarefa, o número do processo, o vértice do grafo. Basta guardar registros no vetor e fazer as comparações apenas no campo da prioridade. As trocas movem o registro inteiro, e os dados viajam junto com a prioridade.

O programa abaixo é um escalonador simples: lê tarefas, cada uma com uma prioridade e um nome, e as executa em ordem de prioridade.

Custos

No heap, alteraFP (com a posição conhecida) custa , tamanhoFP e vaziaFP custam , e a construção a partir de um vetor, . Além disso, o heap não usa ponteiros: os elementos ficam lado a lado no vetor, o que o torna, na prática, bem mais rápido que uma árvore balanceada.

Exercícios

Encontre e corrija o erro

Os programas abaixo constroem um heap a partir do vetor (3, 1, 5, 8, 2, 4, 7, 6, 9), o da figura da construção, e depois removem o máximo até esvaziar a fila. Uma função ehHeap confere a propriedade de ordem. Cada programa tem um erro diferente.

Programa 1

if (r <= fp->tamanho && fp->A[r] > fp->A[maior])
    maior = r;

Programa 2

for (int i = fp->tamanho / 2; i >= 1; i--)
    corrigeDescendo(fp, i);

Programa 3

troca(&fp->A[1], &fp->A[fp->tamanho]);
fp->tamanho--;

Implemente

Os k maiores. Uma sequência muito longa de valores chega um a um, e queremos saber, a qualquer momento, qual é o -ésimo maior valor visto até ali, e quais são os maiores. Guardar a sequência inteira gasta memória demais. Implemente o TAD de kmaiores.h, com observa em , kesimoMaior em e listaMaiores (os maiores, em ordem decrescente) sem alterar a estrutura, usando memória proporcional a , e não ao tamanho da sequência. Os testes observam até 400 mil valores, com igual a 20 mil, consultando o -ésimo maior a cada valor.

Alterar a prioridade de um elemento identificado. Nesta fila de prioridade, cada elemento é um registro com um identificador (de 0 a ) e uma prioridade, e o TAD oferece alteraFP(fp, id, prioridade): o usuário diz qual elemento, e não em que posição ele está. Para encontrar o elemento em , a fila guarda um vetor pos, em que pos[id] é a posição de id no heap (ou 0, se ele não está na fila). Todo o TAD está pronto, exceto duas funções: troca, que troca dois elementos do heap mantendo pos atualizado, e alteraFP. Os testes conferem o heap e o vetor pos depois das operações, e o último faz 600 mil operações em uma fila com 100 mil elementos.

Referências

• T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein. Algoritmos: Teoria e Prática. 3ª ed. Elsevier, 2012. Capítulo 6.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
• R. Sedgewick e K. Wayne. Algorithms. 4ª ed. Addison-Wesley, 2011. Seção 2.4.
• D. Galles. Visualização interativa do heap. University of San Francisco.