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

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:

	int pai(int i){
	return i/2;
	}

	int esquerda(int i){
	return 2*i;
	}

	int direita(int i){
	return 2*i+1;
	}

view raw

funcoes_heap.cpp

hosted with ❤ by GitHub

Montando uma Heap

Para montar uma Heap, vamos, primeiro, construir duas funções importantes para isso. Chamaremos estas de heapify_u e 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:

	void heapify_up(int v){

	if(v == 1) return; // se estivermos no topo, fazemos mais nada

	int p = pai(v);
	if(heap[v] > heap[p]){

	// se o valor da posição v for maior que o de seu pai,
	// temos que fazer a troca dos dois e chamar a função em p

	swap(heap[v], heap[p]);
	heapify_up(p);
	}
	}

	void heapify_down(int v){

	int d = direita(v);
	int e = esquerda(v);

	int maior = v; // no fim, maior terá a maior das posições

	// comparamos com cada um dos filhos.
	// temos que checar, também, se os filhos existem
	if(d <= tamanho_heap && heap[d] > heap[v]) maior = d;
	if(e <= tamanho_heap && heap[e] > heap[maior]) maior = e;

	if(maior != v){
	// se v não for o maior, temos que trocar com o maior dos filhos
	// e chamamos a função para ele

	swap(heap[v], heap[maior]);
	heapify_down(maior);
	}
	}

view raw

heapify.cpp

hosted with ❤ by GitHub

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:

	void insere(int valor){

	// atualizamos o tamanho da heap e inserimos no fim do array
	tamanho_heap++;
	heap[tamanho_heap] = valor;

	// agora, chamamos o heapify_up
	heapify_up(tamanho_heap);
	}

	void deleta(int posicao){

	// esta função deleta um número e qualquer
	// posição da heap, porém, na prática, só
	// irá ser usada para remover o topo da heap

	// trocamos com o número do fim e atualizamos o tamanho
	swap(heap[posicao], heap[tamanho_heap]);
	tamanho_heap--;

	// chamamos a heapify_down
	heapify_down(posicao);
	}

view raw

heap.cpp

hosted with ❤ by GitHub

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:

	//
	// malabarismo_de_malter.cpp
	//
	// Created by Lucca Siaudzionis on 17/05/15.
	//
	// Malabarismo de Malter - Noic

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	//---------------------
	#define MAXN 1000100

	int heap[MAXN];
	int tamanho_heap;
	//---------------------

	int pai(int i){
	return i/2;
	}

	int esquerda(int i){
	return 2*i;
	}

	int direita(int i){
	return 2*i+1;
	}

	void heapify_up(int v){

	if(v == 1) return;

	int p = pai(v);
	if(heap[v] > heap[p]){
	swap(heap[v], heap[p]);

	heapify_up(p);
	}

	}

	void heapify_down(int v){

	int d = direita(v);
	int e = esquerda(v);

	int maior = v;

	if(d <= tamanho_heap && heap[d] > heap[maior]) maior = d;
	if(e <= tamanho_heap && heap[e] > heap[maior]) maior = e;

	if(maior != v){
	swap(heap[v], heap[maior]);

	heapify_down(maior);
	}
	}

	void insere(int valor){
	heap[++tamanho_heap] = valor;

	heapify_up(tamanho_heap);
	}

	void deleta(int posicao){

	swap(heap[posicao], heap[tamanho_heap]);
	tamanho_heap--;

	heapify_down(posicao);
	}

	int main(){

	int n;
	scanf("%d", &n);

	for(int i = 1;i <= n;i++){

	char operacao;
	scanf(" %c", &operacao);

	if(operacao == 'I'){ // inserir um número
	int valor;
	scanf("%d", &valor);

	insere(valor);
	}

	if(operacao == 'D'){
	printf("%d\n", heap[1]); // imprime o valor do topo
	deleta(1);
	}

	}

	return 0;
	}

view raw

malabarismo_de_malter.cpp

hosted with ❤ by GitHub

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:

	//
	// malabarismo_de_malter.cpp
	//
	// Created by Lucca Siaudzionis on 17/05/15.
	//
	// Malabarismo de Malter - Noic

	#include <queue>
	#include <cstdio>
	using namespace std;

	//------------------------
	int n;
	priority_queue<int> heap;
	//------------------------

	/*
	OBS:

	Se quiser declarar uma min heap ao invés de uma max heap, declare assim:

	priority_queue< int, vector<int>, greater<int> > heap;

	*/

	int main(){

	scanf("%d", &n);

	for(int i = 1;i <= n;i++){

	char operacao;
	scanf(" %c", &operacao);

	if(operacao == 'I'){ // inserir um número
	int valor;
	scanf("%d", &valor);

	heap.push(valor);
	}

	if(operacao == 'D'){
	printf("%d\n", heap.top()); // imprime o valor do topo
	heap.pop();
	}

	}

	return 0;
	}

view raw

malabarismo_de_malter2.cpp

hosted with ❤ by GitHub

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.