Filas de prioridades (heap) para o CNU (TI)

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:

• Introdução às Filas de Prioridade
• O que é um Heap?
• Tipos de Heap
• Propriedades do Heap
• Como implementar um Heap?
• Operações com Heap: Passo a Passo
• Aplicações de Heaps
• Conclusão

Introdução às Filas de Prioridade

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.

O que é um Heap?

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.

Tipos de Heaps

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.

Propriedades do Heap

As propriedades fundamentais de um heap são:

• Propriedade de Estrutura: Um heap é uma árvore binária completa, preenchida da esquerda para a direita. Uma árvore completa é aquela em que todos os níveis da árvore estão completamente preenchidos, exceto possivelmente o último nível.
  
• Propriedade de Heap: Em um heap máximo, o valor de um nó é maior ou igual ao valor de seus filhos. E o oposto é verdadeiro para um heap mínimo.

Essas propriedades garantem que o elemento de maior (ou menor) prioridade esteja sempre na raiz do heap, permitindo um acesso rápido e eficiente.

Como um heap é implementado?

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:

• O pai de i está em i / 2. Caso o resultado seja um decimal, considere somente a parte inteira. Por exemplo, para encontrarmos o pai do nó de índice 1 fazemos o seguinte cálculo: 1 / 2 = 0,5. Assim, o pai terá o índice 0, pois a parte inteira de 0,5 é 0 (zero).
• O filho esquerdo de i está em 2*i.
• O filho direito de i está em 2*i+1.

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:

• Pai: (i – 1)/2.
• Filho esquerdo: 2*i + 1;
• Filho direito: 2*i + 2;

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.

Operações com Heap: Passo a Passo

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.

Métodos básicos para reorganização de um heap

Propagação para cima (subida ou sift-up)

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.

Propagação para baixo (descida ou sift-down)

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.

Principais operações

Inserção

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:

1. Adição ao final: O novo elemento é adicionado ao final do vetor que representa o heap.

2. Propagação para cima ou subida: O elemento recém-adicionado é comparado com seu pai. Se o novo elemento tiver uma prioridade maior (ou menor, dependendo do tipo de heap), ele é trocado com o pai. Esse processo é repetido até que a propriedade de heap seja restaurada.

Exemplo:

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 é:

Remoção

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:

1. Localização do Elemento a Ser Removido: Determine a posição do elemento que será removido no vetor que representa o heap. Isso pode ser feito usando uma busca linear ou mantendo um mapa de índices para os elementos no heap.
   
2. Substituição com o Último Elemento: Troque o elemento a ser removido com o último elemento do heap. Isso preserva a propriedade de árvore completa do heap.
   
3. Reorganização (subida ou descida): Dependendo do valor do elemento que ficou no lugar do elemento removido e de seus novos filhos (se houver), é necessário reorganizar o heap para manter a propriedade de heap.
   1. Se o elemento for menor (em um heap máximo) ou maior (em um heap mínimo) do que seu pai, aplique o processo de sift-up para movê-lo para a posição correta.
   2. Se o elemento substituído for maior (em um heap máximo) ou menor (em um heap mínimo) do que pelo menos um de seus filhos, aplique o processo de sift-down para movê-lo para a posição correta.

Exemplo de remoção:

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).

Atualização

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:

1. Localização do elemento: O elemento a ser atualizado é localizado no heap.

2. Atualização da prioridade: A prioridade do elemento é alterada conforme necessário.

3. Reorganização: Dependendo da mudança na prioridade, podem ser necessárias operações adicionais, como propagação para cima ou para baixo, para garantir que as propriedades de heap sejam mantidas.

Exemplo:

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.

Aplicações de Heaps

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:

• Algoritmos de Ordenação: Heapsort é um algoritmo de ordenação eficiente baseado em heap.
• Algoritmos de Grafos: Algoritmos como Dijkstra e Prim usam filas de prioridade para seleção eficiente de arestas ou vértices.
• Gerenciamento de Memória: Heaps são usados em alocação de memória dinâmica, como no algoritmo de alocação de memória de primeira adaptação.

Conclusão

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!

Concursos abertos

Concursos 2024