06/05/2010

1

Análise e Complexidade d Al itde AlgoritmosAlgoritmos de árvores

- binária- avl

ó B- arvóre B- heap

http://www.bolinhabolinha.comProf. Rodrigo Rochaprof.rodrigorocha@yahoo.com

Onde Estamos

Ementa• Revisão:

Estrutura de dados;Crescimento de funções;

Indução matemática e métodos matemáticos Indução matemática e métodos matemáticos.

Medidas de complexidade, análise assintótica de limites de complexidades.

Exemplos de análise de algoritmo iterativos e recursivos.

Análise de desempenho de alguns algoritmos clássicos de busca e ordenação.

Introdução aos principais paradigmas do projeto de algoritmos.

Complexidade do Problema: Limites de Complexidade, Intratabilidade, Classes P, NP, problemas Np completos e NP-difíceis.

06/05/2010

2

Árvores

É uma estrutura de dados hierárquica• Exemplo

chave de times em um campeonato

á ló iárvore genealógica

organograma funcional

Componentes• raiz (root) – nó superior

• aresta – linha que liga os nós

• folhas – nós filhosfolhas nós filhos

• floresta – conjunto de árvores

• grau do nó - número de nós filhos

• grau da árvore - é o máximo entre os graus de seus nós

Árvores

Operações procura, predecessor, antecessor, mínimo, máximo,

inserir e deletar

Idealmente, temos– Árvore balanceada

» Red black, avl, b tree

– Altura: log n para n nós

armazenamento– Muito grande para RAM

– Parte em RAM, parte em méio magnético

» Meio magnético + lento

06/05/2010

3

Árvores binárias

Estrutura de dados: árvore• cada nó tem no máximo duas sub árvores

• Operações procura, predecessor, antecessor, mínimo, máximo, inserir e

deletar

Tempo é proporcional a altura da árvore

Estrututa• Campo chave

• Campo esquerdop q

• Campo direito

• P = pai

Se algum filho ou pai estiver ausente, o campo conterá nulo• O nó raiz é o único que contém o campo pai nulo

Árvores binárias

Implementando em um vetor• Array com 7 posições:

• Armazenamento por nível: • posição do nó posição dos filhos do nó

1 2,3

2 4,5

3 6,7

i (2i,2i+1)

06/05/2010

4

Árvores binárias

Implementando em uma estrutura• campo do valor

• 2 ponteiros : para o filho da esquerda e direita2 ponteiros : para o filho da esquerda e direita

• Estrutura (exemplo)typedef struct sttNo {

tipo inf; struct sttNo *esq, *dir;

} tNo;

Árvores binárias

Procedimento para imprimir todos os elementos de uma árvore binária

INORDER-TREE-WALK(x)

if x ≠ NIL

then INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])

Complexidadep• ɵ(n)Pois, após a chamada ao procedimento inicial, o

procedimento é chamado de forma recursiva duas vezes (filho da direita e filho da esquerda)

06/05/2010

5

Árvore Binária de Pesquisa

Árvore binária de pesquisa• nós são distribuídos de forma a facilitar a

pesquisap q

• Para qualquer nó xelementos a esquerda são menores que o elemento pai

elementos a direita são maiores que o elemento pai

Árvores binárias

PesquisandoTREE-SEARCH(x, k)

if x = NIL or k = key[x]

then return xthen return x

if k < key[x]

then return TREE-SEARCH(left[x], k)

else return TREE-SEARCH(right[x], k)

Chamada inicial: TREE-SEARCH(root[T ], k).

Para procurar a chave 13• 15-6-7-13

06/05/2010

6

Árvores binárias

Versão não recursiva do algoritmoITERATIVE-TREE-SEARCH(x, k)

1 while x ≠ NIL and k ≠ key[x]

2 do if k < key[x]2 do if k < key[x]

3 then x ← left[x]

4 else x ← right[x]

5 return x

Complexidade• Relativa a altura da árvore O(altura)

• Se a árvore estiver balanceada para 1000 elementos, 10 comparações

O (log n)

• SenãoO (n)

Árvores binárias

Máximo e mínimo valor TREE-MINIMUM(x)

while left[x] = NIL

do x ← left[x]

treturn x

TREE-MAXIMUM(x)while right[x] = NIL

do x ← right[x]

return x

Complexidade• O(h), onde h é a altura da árvore

06/05/2010

7

Sucessor e Predecessor• TREE-SUCCESSOR(x)

if right[x] = NIL

then return TREE-MINIMUM(right[x])

Árvores binárias

( g [ ])

else y ← p[x]

while y = NIL and x = right[y] do

x ← y

y ← p[y]

return y

• Atenção: Os algoritmos de sucessor, mínimo, máximo e predecessor não procuram

pelos valores

Árvores binárias Inserção

• ache a folha que será inserido o nó• conecte o nó ao pai da folha

Algortimo• TREE INSERT (T z)• TREE-INSERT (T, z)• y ← NILx ← root [T]while x ≠ NIL do

y ← xif key [z] < key[x]

then x ← left[x]else x ← right[x]

p[z] ← yif y = NILif y = NIL

then root [T] ← zelse if key [z] < key [y]

then left [y] ← zelse right [y] ← z

Complexidade relativa a altura O(h) h=altura

06/05/2010

8

Árvores binárias

Remoção • nó sem filhossomente ajustamos o ponteiro do nó paij p p

Árvores binárias

Remoção • nó com um único filhomover o filho para a posição do nó paip p ç p

06/05/2010

9

Árvores binárias

Remoção • nó com dois filhos

procuramos o sucessor (ou predecessor), que deverá ocupar o seu lugarlugar

– nó mais a esquerda da sub-árvore da direita

– como ele não tem filhos a esquerda, a sua sub-árvore a direita pode ser movida

Árvores binárias Remoção Algoritmo

TREE-DELETE (T, z)if left [z] = NIL .OR. right[z] = NIL

then y ← z else y ← TREE-SUCCESSOR (z)

if left [y] ≠ NIL then x ← left[y] else x ← right [y]

if x ≠ NIL then p[x] ← p[y]

if p[y] = NIL then root [T] ← x else if y = left [p[y]]

then left [p[y]] ← xthen left [p[y]] ← x else right [p[y]] ← x

if y ≠ z then key [z] ← key [y]

if y has other field, copy them, too return y

Complexidade relativa a altura O(h) h=altura

06/05/2010

10

Árvores binárias

Exercício• Para a árvore abaixo representada, responda as

seguintes questões:g q

• Número de elementos

• Altura

• Elemento Root (Pai)

• Elementos folhas

Árvores binárias - exercícios 1-) Desenhe a árvore de pesquisa binária, com os itens

S,U,P,E,R,F,A,C,I,L. Onde cada nó tenha somente uma letra.

2 ) (12 1 1 Cormen): Trace as árvores de pesquisa binária de 2-) (12.1.1 Cormen): Trace as árvores de pesquisa binária de altura 2,3,4,5 e 6 sobre o conjunto de chaves {1,4,5,10,16,17,21}

3-) Para a árvore binária abaixo, mostre os elementos que serão mostrados, utilizando o algoritmo INORDER-TREE-WALK( )WALK(x)

06/05/2010

11

Exercícios

4-) Escreva o algortimo tree-predecessor.

5 ) Qual a complexidade dos algortimos de 5-) Qual a complexidade dos algortimos de sucessor e predecessor? Explique como você chegou nesta complexidade.

Exercícios

6-) Para a seguinte árvore binária, responda as questões

a-) Mostre os nós que são percorridos para achar o nó com valor 9. O que o algoritmo retornou?) q p p q gb-) Mostre os nós que são percorridos para achar o nó com valor 8. O que o algoritmo retornou?c-) Ache o sucessor de 15. (Mostre os nós que o algoritmo percorreu)d-) Ache o sucessor de 6 . (Mostre os nós que o algoritmo percorreu)e-) Ache o sucessor de 4 . (Mostre os nós que o algoritmo percorreu)f-) Ache o predecessor de 6 . (Mostre os nós que o algoritmo percorreu)g-) Insira o valor 19. (Mostre os nós que o algoritmo percorreu)h-) Insira o valor 1. (Mostre os nós que o algoritmo percorreu)i-) Remova o nó com valor 13. Desenhe o novo layout da árvorej-) Remova o nó com valor 6. Desenhe o novo layout da árvore

06/05/2010

12

Exercícios

7-) (12.2.1 Cormen) Suponha que você tenha os números de 1 a 1000 em uma árvore binária de busca, e quer localizar o número 363. Qual

üê i b i ã d üê i d óseqüência abaixo não pode ser a seqüência de nós examinados?

a-) 2, 252, 401, 398, 330, 344, 397, 363.

b-) 924, 220, 911, 244, 898, 258, 362, 363.

c-) 925, 202, 911, 240, 912, 245, 363.

d-) 2, 399, 387, 219, 266, 382, 381, 278, 363.

e-) 935, 278, 347, 621, 299, 392, 358, 363.

8-) Escreva um algoritmo que traga a soma de todos os valores de uma árvore. Qual a sua complexidade? Justifique.

Demo

Animações na web• http://www.engin.umd.umich.edu/CIS/course.des/c

is350/treetool/

• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BSTNew.html

• http://www cosc canterbury ac nz/mukundan/dsal/• http://www.cosc.canterbury.ac.nz/mukundan/dsal/BST.html

06/05/2010

13

Árvores Balanceadas (AVL)

Árvore binária de pesquisa

Balanceadas pela altura• Para cada nó na árvore, a altura das sub-árvores da direita

e esquerda diferem em no máximo 1

Fator de balanceamento

FB(n) = altura(sadireita) – altura(saesquerda).• se FB(n) = 0, as duas sub-árvores têm a mesma

altura;

• se FB(n) = -1, a sub-árvore esquerda é mais alta que a direita em 1;

• se FB(n) = +1, a sub-árvore direita é mais alta que a esquerda em 1.

06/05/2010

14

Balanceando

Resolvemos o desbalanceamento efetuandorotações• SimplesSimplesSinais (fb) são iguais

• DuplaSinais (fb) são diferentes

• Direita• DireitaFB (+) positivo

• EsquerdaFB (-) Negativo

Operações

Inserção e Remoção• Na maioria dos casos é igual em árvores binárias

de pesquisap q

• Somente muda se desbalancear a árvores, que deverá ser balanceada (rotações)

• Qual a sua complexidade?• Qual a sua complexidade?

• Faça o próximo exercício e tente chegar na complexidade de inserção e remoção.

06/05/2010

15

Exemplos

Inserir 3,2,1,4,5,6,7

Exemplos

Inserir 3,2,1,4,5,6,7

Rotação Simples

3

Fig 1

3

2

Fig 2

3

2

1

2

1 3Fig 4

2 2

Fig 31 3

4Fig 5

1 3

4

5

Fig 6

Simples

06/05/2010

16

2

1 4

53

2

1 4

53

Rotação simples

Fig 7 6Fig 8

4

2 5

61 3

4

2 5

61 3

Rotação simples

1 3

Fig 9

1 3

7Fig 10

4

2 6

71 3

5 Fig 11

Exercício

Criar a árvore binária de pesquisa e uma AVL com os seguintes valores

78 95 63 73 51 3178,95,63,73,51,31

E

78 95 63 105 83 100 78,95,63,105,83,100

06/05/2010

17

Solução

2

0

51 73

9563

78

51 73

9563

78

31

51 78

95

63

73

1

1

0

1

Rotação a Direita

31

-2

10583

9563

78

10583

9563

78

100

-1

1 10578

95

63 83 100

Rotação esquerda

100

06/05/2010

18

Inserção e Deleção

Complexidade de Tempo• Achar o local da inserçãoO (log n)( g )

• Checar se a rotação é necessáriaO(1)

• Checar e rotacionar os seus ancestraisO(log n)

O(log n)

Animações na WEB

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

http://www strille net/works/media technologyhttp://www.strille.net/works/media_technology_projects/avl-tree_2001/

06/05/2010

19

B-Tree Árvores balanceadas

trabalham com dispositivos secundários de armazenamento (ex. disco rígido)• quando o acesso é feito em meio físico a velocidade é prejudicada

devemos tentar minimizar estes acessos

Cada nó tem um número variável de chaves e filhos

As chaves são armazenadas em ordem crescente

Cada chave tem um filho associado que é o root da sub-árvore contendo todos os nós com chave menor ou igual a chave,mas maior que a chave predecessora

Um nó também tem o filho mais a direita sendo o root da subárvore contendo todas as chaves maiores que qualquer chave no nó

B-Tree Fator de minimização

• Uma b-tree tem um número mínimo de filhos para cada nó, conhecido como fator de minimização. Se t é o fator de mínimização, cada nó deve ter pelo menos t-1 chaves

Em algumas circustâncias, o nó root poderá violar esta propriedade tendo menos que t-1 chaves

Cada nó pode ter no máximo 2t-1 chaves, ou, 2t filhos

Quando cada nó tem um alto fator de crescimento (muitos filhos), e necessário atravessar vários nós antes de localizar a chave procurada• Se o acesso ao nó requer acesso ao disco a b tree deverá minimizar• Se o acesso ao nó requer acesso ao disco, a b-tree deverá minimizar

estes acessos

• O fator de minimização é normalmente escolhido de forma que o tamanho total de cada nó corresponda a um múltiplo do tamanho do bloco no dispositivo de armazenamento

• Esta escolha simplifica e otimiza o acesso a disco

06/05/2010

20

B-Tree

Exemplo• B-tree com fator de minimização 3 (t=3)mínimo de chaves (t-1) = 2( )

máximo de chaves (2t-1) = 5

máximo de filhos (2t) = 6

B-Tree

B-Tree é uma estrutura de dados ideal: Situações onde todos os dados não podem residir em um

único meio de armazenamento, e acessa um segundo meio de armazenamento que são mais “custosos” (oumeio de armazenamento, que são mais custosos (ou consomem mais tempo)

06/05/2010

21

B-Tree

Criação• A operação de criação, cria uma árvore B

alocando um nó root sem valores e sendo t bé f lhtambém folhaComplexidade O(1)

B-Tree-Create(T)

x <- Allocate-Node()l f[ ] < TRUEleaf[x] <- TRUEn[x] <- 0Disk-Write(x)root[T] <- x

B-Tree Pesquisa

• Semelhante a pesquisa em árvore binária. • O filho correto é escolhido realizando uma busca linear nos valores do nó. (esquerda os

menores, a direita os maiores) Depois de achado o valor maior ou igual ao valor desejado, seguimos o filho a esquerda e

realizamos novamente a pesquisa• Se todos os valores são menores que o procurado o maior filho a direita e seguido• Se todos os valores são menores que o procurado, o maior filho a direita e seguido

• Complexidade depende do tamanho da árvore. logo O(log n)• B-Tree-Search(x, k)

• i <- 1• while i <= n[x] and k > keyi[x]• do i <- i + 1• if i <= n[x] and k = keyi[x]• then return (x, i)( , )• if leaf[x]• then return NIL• else Disk-Read(ci[x])• return B-Tree-Search(ci[x], k)

• Supomos que no segundo estágio, todos os nós estão armazenados em disco• Outra busca binária em seus filhos => O(lg(t))• => O (log(t) log (n) )

06/05/2010

22

B-Tree Exemplo

• Pesquisando o valor 21

B-Tree Inserção

• O nó apropriado para a inserção é localizado (algoritmo similar ao B-Tree-Search)

• A chave é inserida no nó• Se o nó não está cheio, a chave é inserida sem nenhuma outra ,

operação• caso contrário, o nó deverá ser dividido para acomodar a nova chave

a operação de divisão consistem em mover uma das chaves para o nó PAI, este não pode estar cheio também, caso isso ocorra, outra operação de divisão deverá ser realizada.

• Se cada acesso ao nó pode custar um acesso ao disco, e recomendado que o pai nunca esteja cheio.

• Para satisfazer essa situação, o algoritmo divide qualquer nó que estiver cheio quando estiver percorrendo a árvore para efetuar aestiver cheio quando estiver percorrendo a árvore para efetuar a inserção. As operações de divisão aumentam, mas você garante que o Pai nunca

estará lotado

• Complexidade, desde que a operação de divisão rode em O(n), a inserção rodará em O(t log n)

06/05/2010

23

B-Tree

B-Tree-Insert(T, k)

r < root[T]

B-Tree-Insert-Nonfull(x, k)

i <- n[x]r <- root[T]if n[r] = 2t - 1

then s <- Allocate-Node()root[T] <- s

leaf[s] <- FALSEn[s] <- 0c1 <- rB-Tree-Split-Child(s, 1, r)B-Tree-Insert-Nonfull(s, k)else B-Tree-Insert-Nonfull(r, k)

i <- n[x]if leaf[x]

then while i >= 1 and k < keyi[x]do keyi+1[x] <- keyi[x]

i <- i - 1keyi+1[x] <- k

n[x] <- n[x] + 1Disk-Write(x)else while i >= and k < keyi[x]

do i <- i - 1else B Tree Insert Nonfull(r, k)i <- i + 1Disk-Read(ci[x])if n[ci[x]] = 2t - 1

then B-Tree-Split-Child(x, i, ci[x])if k > keyi[x]

then i <- i + 1B-Tree-Insert-Nonfull(ci[x], k)

B-Tree Divisão do nó (split)

• Se o nó está cheio, é necessário dividí-lo. • Movemos a chave média do nó x para seu pai y• Um novo nó z, torná-se o filho imediatamente a direita da chave média x que foi deslocada para o pai y• e o nó original x, torná-se o filho imediatamente a esquerda da chave média que foi deslocada para y• Esta operação transforma o nó com 2t-1 chaves em dois nós com t-1 chaves cada.• Atenção: Somente uma chave foi movida para o pai.• Complexidade O(t), onde t é constanteComplexidade O(t), onde t é constante

B-Tree-Split-Child(x, i, y)z <- Allocate-Node()leaf[z] <- leaf[y]n[z] <- t - 1for j <- 1 to t - 1

do keyj[z] <- keyj+t[y]if not leaf[y]

then for j <- 1 to tdo cj[z] <- cj+t[y]

n[y] <- t - 1n[y] < t 1for j <- n[x] + 1 downto i + 1

do cj+1[x] <- cj[x]ci+1 <- zfor j <- n[x] downto i

do keyj+1[x] <- keyj[x]keyi[x] <- keyt[y]n[x] <- n[x] + 1Disk-Write(y)Disk-Write(z)Disk-Write(x)

06/05/2010

24

B-Tree Exemplo

• Inserindo o valor 33, em uma árvore de faor de minimização t=3

B-Tree

Remoção1. Se a chave não estiver numa folha, troque-a com seu sucessor

imediato.

2. Elimine a chave da folha.2. Elimine a chave da folha.

3. Se a folha continuar com o número mínimo de chaves, fim.

4. A folha tem uma chave a menos que o mínimo. Verifique as páginas irmãs da esquerda e direita:

– 4.1.se uma delas tiver mais que o número mínimo de chaves, aplique redistribuição.

– 4.2.senão concatene a página com uma das irmãs e a chave pai.

5 Se ocorreu concatenação aplique passos de 3 a 6 para a5. Se ocorreu concatenação, aplique passos de 3 a 6 para a página pai.

6. Se a última chave da raiz for removida, a altura da árvore diminui.

• Fonte: usp (http://www.icmc.sc.usp.br/manuals/sce183/btree4.html)

06/05/2010

25

Exercícios 1-) Onde b-trees são utilizadas? Dê exemplo de aplicações que façam

uso delas.

2-) (usp) Explique a seguinte sentença: "B-Trees são construídas de baixo para cima enquanto árvores binárias são construídas de cima parabaixo para cima, enquanto árvores binárias são construídas de cima para baixo".

3-) Pesquise e descreva o processo de remoção.

4-) Crie uma árvore B de grau 2, com os seguintes valores {1, 2, 3, 4, 5}

5-) Para quais valores de t a árvore B abaixo é válida5 ) Para quais valores de t, a árvore B abaixo é válida.

.

Exercícios 6-) Para a árvore B abaixo,com t=2, responda as seguintes questões:

• Qual o número mínimo de itens?• Qual o número máximo de itens?• Quando o nó é dividido?• Insira os valores 42, 8, 14

D h á d i d i ã• Desenhe a árvore depois da inserção

7-) Construa a b-tree com os seguintes valores. (inseridos nesta ordem)) g ( )• Escolha um grau para a árvore B e informe-o antes da sua construção• a-) 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45• b-) 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56

8-) Utilizando a árvore B criada no exercício 7a:• Adicione as chaves : 2, 6,12• Remova as chaves: 4, 5, 7, 3, 14

06/05/2010

26

Demonstração

Animações na web• http://slady.net/java/bt/view.php?w=600&h=450

Heap Estrutura de dados especial baseada em árvore binária

Propriedades do heap• uma árvore “quase” completa, ou seja todos os seus níveis estão

completos, com exceção do último que pode não estarcompletos, com exceção do último que pode não estar

• Se B é um filho de A, então chave(A) >= chave(B).

• Isto implica que: o elemento com a maior chave, está sempre no nó pai

• Chamado de heap máximo

Também existe a implementação do heap mínimo

O elemento maior(ou menor) sempre fica na raizO e e e o a o (ou e o ) se p e ca a a

Importantíssimo para:• Fila de prioridade

• Algortimos gráficos

06/05/2010

27

Heap

Estrutura• altura da heap = Ө(log n)

Implementação• vetor

raiz = A[1]

pai A[i] = [ � i/2⌡]

filho da esquerda A[i] = A[2*i]

filho da direita A[i] = A[2*i+1]

MAX-HEAPIFY Devemos sempre manter a propriedade do heap máximo

• Antes de MAX-HEAPIFY, A[i] pode ser menor que seus filhos.• Assumimos que a árvore a esquerda e direita de i são heap

máximos• Depois de MAX-HEAPIFY, sub-árvore de pai i é heap máximo

Funcionamento de MAX-HEAPIFY:

• Comparar A[i], A[ESQUERDA(i)], e A[DIREITA(i)].• Se necessário, trocar A[i] com o maior valor entre os filhos,

preservando as propriedades do heap• Continua o processo de comparação e troca nos níveisContinua o processo de comparação e troca nos níveis

inferiores da árvore, até a subárvore de i ser heap máximo. Se temos uma folha, ela já está no heap máximo

06/05/2010

28

Algoritmo Algoritmo

Max-Heapify (A, i)

1 l = Left (i)1 l = Left (i)

2 r = Right (i)

3 if l ≤ heap-size[A] and A[l] > A[i]

4 then largest = l

5 else largest = i

6 if r ≤ heap-size[A] and A[r] > A[largest]

7 then largest = rg

8 if largest <> i then

9 exchange A[i] = A[largest]

10 Max-Heapify (A, largest)

Exemplo Exemplo

• Max-Heapify(A,2), onde tamanho do heap=10

• A[2] viola a propriedade de heap máximo b-) A propriedade de heap máximo e restaurada

c ) depois de chamada recursiva o nó A[4] também é consertado c-) depois de chamada recursiva, o nó A[4] também é consertado

Complexidade : O(log n)

06/05/2010

29

Construção da árvore heap

Construindo uma árvore heap a partir de um vetor desordenado

Complexidade: realiza n/2 vezes Max-Heapify (log n) = O(n log n)

BUILD-MAX-HEAP

06/05/2010

30

Operações

Inserção• inserir o valor 15 na posição X

• violou a propriedade do heap (15>8), logo é trocado

• continua violando a propriedade do heap (15>11), troco novamente

• Complexidade: O(log n)

Operações

Remoção da raiz• basicamente efetuamos a remoção

da raiz e troco pelo último elemento do vetorelemento do vetor

• removo a raiz e troco pelo elemento 4 (último elemento do vetor)

• violou a propriedade do heap (4<8), p p p ( ),logo é trocado

• Complexidade: O(log n)

06/05/2010

31

HeapSort

Algoritmo• Dado um vetor como entrada:

Construímos o heap máximo a partir do vetor

C d ó i ( l t á i ) l it lComeçando na nó raiz (elemento máximo), o algoritmo coloca o maior elemento em seu lugar correto no vetor, trocando-o com o elemento da última posição do vetor

“Descartamos” o último nó (sabendo que ele já está no lugar correto) diminuindo o tamanho do heap e chamando MAX-HEAPIFY na nova raiz (possivelmente está no lugar incorreto)

Repetimos a operação de descarte até restar um nó (o menor elemento) e ele se encontrar na posição corretaelemento), e ele se encontrar na posição correta

• ComplexidadeConstruímos o heap máximo O(n log n)

Repetidamente, removemos o elemento root e trocamos com o último elemento O(log n)

= O (n log n)

Exemplo

Exemplo

06/05/2010

32

Exercícios 1-) Represente as árvores binárias abaixo utilizando vetor. Qual destas árvores não pode ser denominadas heap máximo?

Justifique.

2-) Utilizando aritmética, calcule o índice do vetor para:• Pai de A[9] • nó esquerdo de A[2] • nó direito de A[2]

3-) Para o vetor a seguir, construa a árvore que o represente. Esta árvore é do tipo heap máximo? Por que?

.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

99 90 85 71 72 66 69 32 45 50 41 20 14 11 5

Exercícios 4-) Crie uma árvore heap máximo a partir do vetor abaixo.

• Desenhe cada inserção. S houve troca, indicar a troca efetuada.

5 ) Na árvore do exercício anterior informe a complexidade das seguintes10 15 7 3 4 25

5-) Na árvore do exercício anterior, informe a complexidade das seguintes operações:• Ilustre as operações• - inserção de um elemento de valor 18• - remover a raiz• - heapsort

6-) Utilizando o vetor do exercício 4, crie (ilustrando graficamente) o heap ) ( g ) pmínimo.

7-) Qual a complexidade de unir duas árvores heap? Justifique.

8-) Por que heap pode ser utilizado como fila de prioridades?

06/05/2010

33

Exercícios

9-) Para a árvore de heap mínimo abaixo, insira o valor 42. Ilustre o processo.

10-) Para a árvore de heap mínimo do exercício anterior, ilustre o processo de remoção do nó com valor 6.

Animações na web

Animação• http://www.cse.ohio-

state.edu/~bondhugu/acads/234-tree/index.shtmlg

• http://www2.hawaii.edu/~copley/665/HSApplet.html