As estruturas de dados são fundamentais na ciência da computação, permitindo a organização eficiente e manipulação de informações. Entre essas estruturas, as filas de prioridade desempenham um papel crucial em uma ampla gama de algoritmos e aplicações. Neste artigo, exploraremos as filas de prioridade, assunto este que está no edital do CNU e já foi cobrado pela banca Cesgranrio. Teremos foco especial na implementação usando uma estrutura de dados conhecida como heap.
Este artigo está organizado da seguinte maneira:
As filas de prioridade são estruturas de dados nas quais os elementos são organizados de acordo com uma determinada prioridade. Essa prioridade pode ser definida por diversos critérios, dependendo da aplicação. Por exemplo, em um sistema de atendimento em um hospital, pacientes com condições mais graves podem ter prioridade sobre aqueles com condições menos urgentes.
Essa flexibilidade torna as filas de prioridade incrivelmente versáteis e aplicáveis em uma variedade de cenários, desde algoritmos de busca até sistemas de gerenciamento de tarefas.
Uma das maneiras mais comuns de implementar filas de prioridade é usando uma estrutura de dados chamada heap. Um heap é uma árvore binária especial, onde cada nó satisfaz uma propriedade específica de ordenação, conhecida como propriedade de heap.
Existem dois tipos principais de heaps: o heap máximo e o heap mínimo.
Em um heap máximo, o elemento de maior valor está sempre na raiz da árvore, enquanto em um heap mínimo, o elemento de menor valor ocupa a raiz.
As propriedades fundamentais de um heap são:
Essas propriedades garantem que o elemento de maior (ou menor) prioridade esteja sempre na raiz do heap, permitindo um acesso rápido e eficiente.
A implementação de um heap pode ser feita de várias maneiras, mas uma das mais comuns é usando um vetor. Nessa abordagem, os elementos do heap são armazenados em um vetor, onde a relação de pai-filho é mantida através do cálculo de índices.
Considerando um heap em um vetor, com este iniciando com índice 1 (um), para um nó armazenado no índice i desse vetor:
Perceba que estamos considerando que o heap começa pelo índice 1. Caso o heap inicie com o índice 0 (zero), os valores serão:
Para todos os exemplos aqui explicitados, iremos considerar que o heap inicia com pelo índice 1.
A seguir temos um exemplo de um heap em uma estrutura de árvore:
Agora, temos o mesmo heap representado por um vetor:
Pela estrutura de árvore fica fácil identificar os nós, seu pai e seus filhos. Por outro lado, a partir do vetor, é necessário utilizarmos as fórmulas apresentadas anteriormente.
Por exemplo, qual seria o pai e os filhos do elemento de valor 17 (índice 3)?
Claro que observando pela árvore é mais fácil de localizar. Mas em provas de concursos, normalmente o vetor é fornecido e deve-se indicar os elementos a partir dele.
Agora que compreendemos os conceitos básicos de heaps e suas propriedades, vamos explorar detalhadamente como são realizadas as operações principais em um heap: inserção, remoção e atualização.
Se um elemento tiver uma prioridade maior que o pai, ele é trocado de posição com o pai. Esse processo é repetido até que a propriedade de heap seja restaurada.
Se um elemento tiver uma prioridade menor que os filhos, ele é trocado filho de maior prioridade. Esse processo é repetido até que a propriedade de heap seja restaurada.
A operação de inserção em um heap envolve adicionar um novo elemento e garantir que as propriedades de heap sejam mantidas. Vamos seguir o seguinte passo a passo:
Passo 1: Adicionar o novo valor ao final da heap
Comece com a heap original: [90, 36, 17, 25, 26, 7, 1, 2, 3, 19].
Adicione o novo valor 40 ao final da lista, resultando em: [90, 36, 17, 25, 26, 7, 1, 2, 3, 19, 40].
Passo 2: Restaurar a propriedade de heap
O valor 40 está na última posição (índice 11) da heap.
Compare 40 com seu pai, que está na posição 11 // 2 = 5.
Como 40 > 26, a propriedade de heap não é satisfeita. Troque 40 com seu pai 26, movendo 40 para a posição 5 e o 26 para a posição 11.
Passo 3: Repetir a comparação e a troca até a raiz
Compare o novo valor 40 na posição 5 com seu pai 36 na posição 5 // 2 = 2.
Como 40 > 36, a propriedade de heap não é satisfeita. Troque 40 com seu pai 36, movendo 40 para a posição 2.
Compare o valor 40, na posição 2, com seu pai, 90, na posição 1. Como 40 < 90, o processo de comparação e troca termina.
A heap final após a inserção de 40 é:
A operação de remoção em um heap envolve retirar um elemento pelo seu índice, normalmente elemento de maior (ou menor) prioridade e garantir que as propriedades de heap sejam mantidas. Normalmente é removido o elemento raiz, mas qualquer elemento pode ser removido. Vamos seguir o seguinte passo a passo:
Vamos considerar a seguinte estrutura:
Árvore heap:
Vetor correspondente:
Passo 1: Elemento a ser removido
Iremos remover o elemento de índice 6 (valor 7).
Passo 2: Substituição com o último elemento
Substituir o elemento a ser removido pelo último elemento, que é o 26, que está no índice 11.
Após a substituição, temos:
Passo 3: Reorganização
Perceba que após a substituição, o elemento de índice 6 (26) é maior que seu pai (17), que está no índice 3. Então, precisamos realizar o movimento de subida ou sift-up:
Após a troca, temos:
Após a troca dos elementos 17 e 26, as propriedades do heap foram satisfeitas, pois o elemento 26 é menor que seu pai (90) e maior que os filhos (17 e 1).
A operação de atualização em um heap envolve alterar a prioridade de um elemento existente e garantir que as propriedades de heap sejam mantidas. Como a operação de atualização é menos comum e depende do contexto específico da aplicação, não existe um método padrão. No entanto, pode-se seguir um processo geral:
Considerando a estrutura heap acima, iremos atualizar o valor 40 (índice 2) para 5.
Passo 1: Localização do elemento. O valor 40 está no índice 2:
Passo 2: Atualização da prioridade, o valor do índice 2 passa a ser 5:
Passo 3: reorganização.
Perceba que a nova estrutura não satisfaz as propriedades do heap, pois o valor 5 é menor que seus filhos. Neste caso, devemos trocar o valor pelo filho de maior valor, em um procedimento de descida (sift-down):
Selecionamos o filho de maior valor, que é o valor 36, índice 5:
Agora, realizamos o procedimento de troca:
A nova estrutura ainda não satisfaz as propriedades do heap, pois o valor 5 (índice 5) é menor que seus filhos,19 e 26, que estão nos índices 10 e 11, respectivamente.
Selecionamos o filho de maior valor, que é 26, índice 11:
Novamente, realizamos o procedimento de troca:
Dessa vez as propriedades do heap foram satisfeitas. Portanto, a operação de atualização foi finalizada.
Os heaps são amplamente utilizados em algoritmos e aplicações que requerem acesso rápido a elementos com prioridade máxima ou mínima. Algumas das aplicações comuns incluem:
As filas de prioridade são estruturas de dados poderosas e versáteis, fundamentais em muitos algoritmos e sistemas. A implementação usando heaps oferece uma solução eficiente e elegante para lidar com tarefas que requerem acesso rápido a elementos com prioridade máxima ou mínima.
Esperamos que este artigo tenha fornecido uma compreensão clara das filas de prioridade e da importância dos heaps em sua implementação. Bons estudos!
Quer saber quais serão os próximos concursos?
Confira nossos artigos!
