Aula 16 - Estruturas de Dados III: Heap (Fila de Prioridade)

0 Flares Facebook 0 0 Flares ×

Aula por Lucca Siaudzionis

"Malter Warinho é um excelente malabarista do Núcleo Organizado de Informática e Computação (NOIC). Um belo momento, ele decidiu usar seu talento para entreter as pessoas. Malter começa com uma sacola (inicialmente vazia) e várias bolas, cada uma com sua determinada massa. Há dois tipos de operação que Malter costuma fazer: inserir uma determinada bola na sacola e remover a bola de maior massa. Ajude Malter a fazer isso de maneira eficiente."

A solução trivial seria manter um array (ou vector) com todas as bolas que há na sacola e, na hora de remover, percorremos toda a sacola a procura da bola de maior número. Assim, a complexidade fica O(1) para inserção e O(N) para remoção (onde N é o número de bolas).

Vamos abordar um método de fazer esse processo de maneira mais rápida.

Heap é uma árvore-binária (ou seja, cada nó possui dois filhos) onde cada nó possui um determinado valor e onde o valor do pai é sempre maior ou igual que o dos filhos (sendo chamada de max heap) ou sempre menor ou igual que o dos filhos (sendo chamada de min heap). Suponha que temos os valores \{1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 11, 12\}. Há diversas maneiras de construirmos uma max-heap que satisfaça isso, olhe os exemplos:

Heap 1

Heap 2

Vemos que as duas heaps possuem os mesmos valores, mas elas aparentam ser bem diferentes. Porém, mesmo com todas as diferenças, um detalhe muito importante permanece o mesmo: o número do topo é o maior de todos.

 

Representação de uma Heap

Uma Heap pode ser representada simplesmente por um array. Porém, a identação tem que ser feita a partir do 1. Para ir preenchendo o array, imagine que se vá preenchendo nível a nível (nos níveis da árvore), preenchendo cada nível da esquerda para a direita. Assim, os dois exemplos anteriores podem ser representados por [12, 10, 11, 8, 8, 5, 9, 4, 3, 6, 5, 1, 2, 7] e [12, 11, 8, 10, 9, 5, 5, 1, 6, 7, 8, 4, 2, 3].

Pode-se, também, observar que, para uma determinada posição i do array, temos que as posições do seus filhos são 2i e 2i+1. Temos também que a posição do seu pai será \left \lfloor {\frac{i}{2}} \right \rfloor. Fazendo o código em C++ disso, temos:

 

Montando uma Heap

Para montar uma Heap, vamos, primeiro, construir duas funções importantes para isso. Chamaremos estas de heapify_u heapify_down. A primeira corrige a estrutura de uma heap subindo, ou seja, começa numa determinada posição e toda vez que o número dessa posição for maior que o pai, troca-se os dois. A segunda faz um processo semelhante, porém descendo pela heap. A heapify_up é importante para inserir números na heap e a heapify_down é importante para remover.

As duas funções funcionam de maneira recursiva, olhe o código das duas:

Agora que temos essas duas funções, inserir ou remover um número da heap começa a ficar algo mais fácil de se pensar. Para inserir um número, basta inserir este na última posição do array e chamar heapify_up nele. Para remover um número, basta trocar este com o último número do array e chamar a função heapify_down na posição (e atualizar o tamanho do array). Os códigos ficam assim:

 

Assim, já temos todo o necessário para resolver o problema do Malabarismo de Malter. Vamos adotar que o número N de operações será N \leq 10^6. O código, então, fica assim:

 

Usando o C++

Na biblioteca <queue> já existe a estrutura priority_queue, que é uma max_heap implementada para você. As funções mais usadas dela são: pop (que remove o elemento do topo), top (que retorna o elemento do topo) e push (que insere um elemento). Assim, o problema do Malabarismo de Malter ficaria assim:

Tenta, agora, resolver os problemas abaixo. Tente implementar a sua própria Heap, sem simplesmente usar a estrutura do C++, para ter certeza que você realmente entende como funciona a estrutura. A priority_queue do C++ é aconselhada quando você realmente entender o conteúdo. Se surgir alguma dúvida na explicação teórica ou você não conseguir resolver algum dos problemas, volte para a página inicial do curso e preencha o fomulário para nos enviar sua dúvida.

Problema 1 - Queue

Problema 2 - Telemarketing (OBI 2007 - P1 Fase 2) - Problema com solução do Noic. Para vê-la, clique aqui.

Problema 3 - Bolsa de Valores

Problema 4 - Banco (OBI 2012 - P2 Fase 2) - Tente fazê-lo de maneira amais rápida que a solução apresentada na aula de pilhas, usando uma heap

Problema 5 - Printer Queue

Problema 6 - Eu Posso Adivinhar a Estrutura de Dados!

Problema 7 - Construção de Procura Binária de Heap


As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.

 

 

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: