bc1435 – Fila de prioridade: Heap

— Fila de prioriodade —

 É uma estrutura abstrata de dados usada para manter um conjunto de elementos {S} com um valor associado a cada elemento, chamado de chave e que quantifica a prioriodade de cada elemento de S. Uma fila de prioridade deve prover as seguintes operações básicas:

  • insere{( x )}: insere o elemento {x} em {S};
  • max: retorna o elemento de {S} de maior prioridade;
  • extraiMax: remove o elemento de {S} com maior prioridade;

o elemento de maior prioridade pode ser o de maior valor de chave (fila com prioridades decrescentes) ou menor valor de chave (fila com prioridades crescentes). A não ser que seja dito o contrário nós consideramos o caso de fila de prioridades decrescentes.

Além dessas operações básicas uma fila de prioridades usualmente  suporta as operações: remover um elemento qualquer, unir duas filas de prioridades, aumentar a prioridade de um elemento e diminuir a prioridade de um elemento.

Há várias maneiras de implementar uma fila de prioridades e, com  isso, ocorre uma variedade de custos na eficiência das operações básicas. Nas implementações mais imediatas alguma das operações básicas é  rápida mas as outras são lentas. O objetivo é projetar uma estrutura de dados na qual todas as operações são eficientes.

Uma maneira eficiente de implementar uma fila de prioridades é usar uma estrutura conhecida como heap.

— Heap binária —

Uma árvore binária {T} é ou a árvore vazia (que não possui vértices), denotada {\emptyset} por abuso de notação, ou é uma terna T=(r,E,D) em que r é um vértice (ou nó) chamado raiz de T e E e D são árvores binárias disjuntas e que não contêm a raiz r, são chamadas subarvore esquerda e subarvore direita, respectivamente. A raiz de E, supondo que E \neq \emptyset, é chamada filho esquerdo de r e a raiz de D, dado que D\neq \emptyset, é chamada filho direito de r. Nos casos das subarvores (f, \emptyset, \emptyset) chamamos {f} de folha, e os vértices não-folha são ditos vértices internos ou nós internos.

O nível de um nó numa árvore binária é definido do seguinte modo: o nível da raiz é {0} e os filhos de um nó de nível {j} estão no nível {j+1} da árvore. A altura de uma árvore é igual ao maior nível de um nó dela e a altura de um nó é a altura da subárvore da qual esse nó é raiz.

Uma árvore binária é quase-completa se todos os níveis exceto os dois últimos, são completos e  o último nível é composto da esquerda para a direita (as folhas fica mais a esquerda possível), assim, é uma árvore binária com altura {d} na qual todas as folhas estão no nível {d} ou {d-1}, e se um nó {v} na árvore tem filho direito no nível {d}, então o filho esquerdo {v} também está no nível {d}, ademais (r, \emptyset, E) com E \neq\emptyset não ocorre como subarvore.

Numa árvore binária quase-completa com altura d o número de nós  no nível i é 2^i para todo i \in \{0,1,\dots,d-1\}, portanto são 2^d -1 nós. No nível {d} são {n-2^d+1} nós, os quais agrupados em 2 resultam em \lceil (n-2^d+1)/2 \rceil nós pais no nível d-1   (dentre os 2^{d-1} nós desse nível). Assim, a quantidade de folhas numa árvore binária quase-completa é

{\displaystyle (n-2^d+1) + 2^{d-1}- \left\lceil \frac{n-2^d+1}{2}\right\rceil =\left\lfloor \frac{n-2^d+1}{2}\right\rfloor + 2^{d-1} =\left\lfloor \frac {n+1}2\right\rfloor  = \left\lceil \frac n2 \right\rceil}.

A altura d em função de n é

d = \lfloor \log_2 n \rfloor

pois 2^d \leq n \leq 2^{d+1} -1, ou seja, { d \leq \log_2 n < d+1}.

Heap é uma estrutura de dados com representação em um vetor {V[1..n]} de uma árvore binária quase-completa. Dado um vetor {V} e um índice {i}, os índices no vetor do pai, filho esquerdo e filho direito são dados por:

  • {\mathrm{pai}(i) = \lfloor i/2 \rfloor};
  • {\mathrm{esq}(i) = 2i};
  • {\mathrm{dir}(i) = 2i+1};

o índice 1 não tem pai;  um índice i só tem filho esquerdo se 2i\leq n e só tem filho direito se 2i+1\leq n. Cada nó {i} tem associado um conteúdo que satisfaz a propriedade da heap:

{V[\mathrm{pai}(i)] \geq V[i]}.

Exemplo:

heap

Exercício 1 Prove que a altura de uma árvore binária quase-completa de {n} nós é { h = \lfloor \log_2 (n) \rfloor} e que o número total de níveis é 1+h.

— Operações —

O seguinte algoritmo é a principal ferramenta no tratamento de heaps. Ele rearranja o vetor V de modo que se E e D são heaps em (i,E,D) então (i,E,D) passa a ser heap.

Faz Heap  em i

 
FazHeap (V[1..n],i)

  Dados um vetor V[1..n] e um índice i de modo que as subarvores
esquerda e direita do elemento i já satisfazem a propriedade heap. 
  Devolve V com subarvore de raiz i satisfazendo a propriedade 
de heap.

1    Se (esq(i) <= n e V[esq(i)] > V[i]) maior <- esq(i) 
2    Senao maior <- i 
3    Se (dir(i) <= n e V[dir(i)] > V[maior]) maior <- dir(i) 
4    Se (maior {\neq} i) V[i] <-> V[maior] 
5    FazHeap (V, maior). 

O número de instruções executadas por FazHeap(V[1..n], i) é uma constante que corresponde às instruções nas linhas 1–4 mais o número de instruções executadas na chmamada recursiva da linha 5. Em função da altura h=h(i) do nó i o número de instruções é

\displaystyle T(h) = T(h-1) + \Theta(1)

logo T(h(i)) = O(h(i)).

A altura no nó {i\in \{1,\dots,n\}} é

\displaystyle h(i) = \lfloor \log_2(n/i) \rfloor

o que pode ser provado por indução em { i}: para { i=1} temos que { h(1)} é a altura da árvore e pelo exercício 1 vale { h(1)=\lfloor \log_2 n \rfloor}.

Suponhamos que { { h(k)=\lfloor \log_2 (n/k) \rfloor}} para todo { k \in \{1,\dots, i-1\}}. Então { h(i) = h(\mathrm{pai}(i)) - 1} e { \mathrm{pai}(i) = \lfloor i/2 \rfloor \in \{1,\dots, i-1\}}, portanto, { h(\mathrm{pai}(i))= \lfloor \log_2 (n/ \lfloor i/2 \rfloor ) \rfloor= \lfloor \log_2 ( \lfloor n/( i/2) \rfloor ) \rfloor = \lfloor \log_2 (n/i) +1\rfloor= \lfloor \log_2 (n/i)\rfloor +1} donde segue que { h(i) = \lfloor \log_2(n/i) \rfloor}.

Portanto, no pior caso, o número de instruções executadas por FazHeap(V[1..n], i) é O(\log_2(n/i)).

O próximo algoritmo usa o FazHeap para que todos os elementos de um vetor satisfaçam a propriedade de heap.

Constrói-Heap 

ConstroiHeap (V[1..n])

   Dado um vetor V[1..n] de inteiros. 
   Devolve V reorganizado de modo a valer a propriedade de heap.

1  Para i de {\lfloor}n/2{\rfloor} até 1 faça 
2                FazHeap(V[1..n],i)

Observemos que todos os elementos com índice maior que {\lfloor n/2 \rfloor} são folhas, portanto, a iteração só precisa tratar os elementos armazenados nos índices menores que esse.

Exercício 2 Mostre que todos os elementos com índice maior que {\lfloor n/2 \rfloor} no vetor são folhas da árvore.

A complexidade de tempo de FazHeap(V[1..n],i) é {O(h(i))}, portanto a complexidade de tempo de ConstóiHeap(V[1..n]) é

\displaystyle \sum_{i=1}^{\lfloor n/2 \rfloor} O(h(i)) =O(n)

pois num heap com {n} itens \displaystyle 0 \leq h(i) \leq \lfloor \log_2(n)\rfloor logo

\displaystyle \sum_{i=1}^{\lfloor n/2 \rfloor} O(h(i))= \sum_{h=1}^{ \lfloor \log_2(n)\rfloor} O(h)\cdot n_h

onde {n_h} é o número de nós na heap que tem altura {h}

Exercício 3 Prove que {\displaystyle n_h = \left\lceil \frac n{2^{h+1}} \right\rceil.}

Agora, usamos que {\left\lceil \frac n{2^{h+1}} \right\rceil < \frac n{2^{h}} } e temos

\displaystyle \sum_{h=1}^{ \lfloor \log_2(n)\rfloor} O(h)\cdot n_h = O \left( \sum_{h=1}^{ \lfloor \log_2(n)\rfloor} h \frac n{2^{h}} \right) = O \left( n\sum_{h=1}^{ \lfloor \log_2(n)\rfloor} \frac h{2^{h}} \right)

e o somatório pode ser estimado como

\displaystyle \sum_{h=1}^{ \lfloor \log_2(n)\rfloor} \frac h{2^{h}} \leq \sum_{h=1}^{ \infty} \frac h{2^{h}} = 1

pois (fazendo {x=1/2})

\displaystyle \sum_{h=1}^{ \infty} h{x^{h}} = \frac{x^2}{(1-x)^2}

para {|x|<1} (procure pela justificativa aqui).

Exercício 4 Use o ConstroiHeap para projetar um algoritmo de ordenação e analise a complexidade desse algoritmo.

Agora, vejamos as operações de fila de prioridade quando essa é implementada por um heap.

Max

 max(V[1..n])

  Dado um vetor V[1..n] de inteiros estruturado como uma heap.
  Devolve o maior elemento.
1   Devolva V[1]

extraiMax 

extraiMax(V[1..n])

   Dado um vetor V[1..n] de inteiros estruturado como uma heap.
   Remove o maior elemento e devolve o  vetor V[1..n-1] estruturado 
como uma heap.

1       V[1] <-> V[n] 
2       FazHeap(V[1..n-1],1) 
3       Devolva(V[1..n-1]).

Inserção

 insere(V[1..n], k)

   Dado um vetor V[1..n] de inteiros estruturado como uma heap e 
um inteiro k.
   Insere k em V e devolve o vetor V[1..n+1] estruturado como 
uma heap.

1    V[n+1] <- k
2    Enquanto (i > 1 e V[pai(i)] < V[i])  
3    { 
4      V[pai(i)] <- V[i] 
5      i <- pai(i) 
6    }

Exercício 5 Determine a complexidade dessas operações.

 

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s