Heaps e Árvores binárias

Prévia do material em texto

Heaps e A´rvores Bina´rias 1 / 59
Heaps e A´rvores Bina´rias
Eduardo Camponogara
Departamento de Automac¸a˜o e Sistemas
Universidade Federal de Santa Catarina
DAS-9003: Introduc¸a˜o a Algoritmos
Heaps e A´rvores Bina´rias 2 / 59
Suma´rio
Introduc¸a˜o
Heapsort
A´rvores Bina´rias
Heaps e A´rvores Bina´rias 3 / 59
Introduc¸a˜o
Suma´rio
Introduc¸a˜o
Heapsort
A´rvores Bina´rias
Heaps e A´rvores Bina´rias 4 / 59
Introduc¸a˜o
Introduc¸a˜o
Heap
Heap Sort e´ algoritmo de ordenac¸a˜o
I Como o Merge Sort, Heap Sort ordena n nu´meros em tempo
Θ(n lg n)
I Ordena no local, necessitando apenas um nu´mero constante
de varia´veis de armazenamento.
A estrutura de dados heap, ale´m de permitir a implementac¸a˜o
do algoritmo Heap Sort, tambe´m pode ser utilizada como uma fila
de prioridades eficiente.
Heaps e A´rvores Bina´rias 5 / 59
Heapsort
Suma´rio
Introduc¸a˜o
Heapsort
A´rvores Bina´rias
Heaps e A´rvores Bina´rias 6 / 59
Heapsort
Heaps
Heaps
Um heap (bina´rio) e´ uma estrutura de dados que pode ser vista
como uma a´rvore bina´ria completa.
1
1
2
2
3
3
44 55 66 77 8
8
9
9
10
10
16
16
14
14
10
10
88 77 99 33 2
2
4
4
1
1
Heaps e A´rvores Bina´rias 7 / 59
Heapsort
Heaps
Heaps
Heaps
I Cada no´ da a´rvore corresponde a um elemento do vetor que
armazena o valor do no´.
I A a´rvore e´ completa em todos os n´ıveis com excec¸a˜o do n´ıvel
mais baixo, o qual e´ completado da esquerda para a direita.
Heaps e A´rvores Bina´rias 8 / 59
Heapsort
Heaps
Heaps
Representac¸a˜o de Um Heap
Um vetor A que armazena um heap e´ um objeto com dois
atributos:
I length[A]: nu´mero de elementos do vetor
I heap size[A]: nu´mero de elementos do heap armazenados em
A.
Heaps e A´rvores Bina´rias 9 / 59
Heapsort
Heaps
Heaps
Representac¸a˜o de Um Heap
I A raiz da a´rvore e´ A[1].
I Dado o ı´ndice i de um ve´rtice, podemos calcular os seguintes
ı´ndices.
Parent(i)
return bi/2c
Left Child(i)
return 2i
Right Child(i)
return 2i + 1
Heaps e A´rvores Bina´rias 10 / 59
Heapsort
A Propriedade Heap
A Propriedade Heap
Propriedade Heap
Para que um vetor A seja heap, cada no´ i , com excessa˜o da raiz,
deve satisfazer a seguinte propriedade:
A[i ] ≤ A[Parent(i)]
I O valor de cada no´ e´ no ma´ximo o valor do seu pai
I O maior elemento do heap esta´ na raiz
I As suba´rvores a partir de qualquer no´ possuem valores
menores ou iguais ao valor do no´
Heaps e A´rvores Bina´rias 11 / 59
Heapsort
A Propriedade Heap
A Propriedade Heap
Altura da A´rvore
I altura de um no´ da a´rvore e´ o nu´mero de arestas no caminho
mais longo do no´ ate´ uma folha da a´rvore.
I altura da a´rvore e´ a altura do no´ raiz.
I Uma vez que um heap induz uma a´rvore bina´ria completa, sua
altura e´ Θ(lg n).
Heaps e A´rvores Bina´rias 12 / 59
Heapsort
A Propriedade Heap
A Propriedade Heap
Mantendo a Propriedade Heap
I O procedimento Heapify e´ fundamental na manipulac¸a˜o de
heaps.
I A entrada e´ o vetor A e um ı´ndice do vetor.
I Quando e´ chamado, assume-se que as a´rvores com raiz em
Left Child(i) e Right Child(i) sa˜o heaps, todavia o elemento
A[i ] pode ser menor do que seus filhos, desta forma violando a
propriedade heap
I O procedimento Heapify recupera a propriedade heap da
a´rvore com raiz em i .
Heaps e A´rvores Bina´rias 13 / 59
Heapsort
A Propriedade Heap
A Propriedade Heap
Heapify
Heapify(A, i)
l ← Left Child(i)
r ← Right Child(i)
if l ≤ heap size[A] & A[l ] > A[i ]
largest ← l
else
largest ← i
if r ≤ heap size[A] & A[r ] > A[largest]
largest ← r
if largest 6= i
exchange A[i ]↔ A[largest]
Heapify(A, largest)
Heaps e A´rvores Bina´rias 14 / 59
Heapsort
A Propriedade Heap
A propriedade heap
Exemplo
1
2 3
4 5 6 7
8 9 10
16
14
10
8
7 9 3
2
4
1
⇒
1
2 3
4 5 6 7
8 9 10
16
14 10
8
7 9 3
2
4
1
Heaps e A´rvores Bina´rias 15 / 59
Heapsort
A Propriedade Heap
A propriedade heap
Exemplo
1
2 3
4 5 6 7
8 9 10
16
14 10
8 7 9 3
2 4 1
O tempo de execuc¸a˜o da operac¸a˜o Heapify e´ precisamente a altura
da a´rvore enraizada no no´ i . Portanto O(h) = O(lg n)
Heaps e A´rvores Bina´rias 16 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
I Podemos utilizar o procedimento Heapify para converter um
vetor A[1, . . . , n], com n = length[A] em um heap.
I Como os elementos do subvetor A[(bn/2c+ 1), . . . , n] sa˜o
folhas da a´rvore, podemos iniciar o procedimento no no´ bn/2c
I Cada Heapify executa em O(lg n), portanto, o Build Heap
executa em tempo O(n lg n).
Build Heap(A)
heap size[A]← length[A]
for j ← bheap size[A]/2c downto 1
Heapify(A, j)
Heaps e A´rvores Bina´rias 17 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
Exemplo
1
2 3
4 5 6 7
8 9 10
16
16
14
14
10
10
8
8
7
7
9
9
3
3
2
2
4
4
1
1
A
⇒
1
2 3
4 5 6 7
8 9 10
16
14
10
8 7
9
3
2
4
1
Heaps e A´rvores Bina´rias 18 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
Exemplo
1
2 3
4 5 6 7
8 9 10
16
14
10
8 7
9
3
2
4
1
⇒
1
2 3
4 5 6 7
8 9 10
1614 10
8 7
9
3
2
4
1
Heaps e A´rvores Bina´rias 19 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
Exemplo
1
2 3
4 5 6 7
8 9 10
1614 10
8 7
9
3
2
4
1
⇒
1
2 3
4 5 6 7
8 9 10
1614
10
8 7
9 3
2
4
1
Heaps e A´rvores Bina´rias 20 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
Exemplo
1
2 3
4 5 6 7
8 9 10
1614
10
8 7
9 3
2
4
1
⇒
1
2 3
4 5 6 7
8 9 10
16
14
10
8
7 9 3
2
4
1
Heaps e A´rvores Bina´rias 21 / 59
Heapsort
Construindo Um Heap
Construindo Um Heap
Exemplo
1
2 3
4 5 6 7
8 9 10
16
14
10
8
7 9 3
2
4
1
⇒
1
2 3
4 5 6 7
8 9 10
16
14 10
8 7 9 3
2 4 1
Heaps e A´rvores Bina´rias 22 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Algoritmo de Ordenac¸a˜o
O algoritmo Heapsort
Heapsort(A)
Build Heap(A)
for i ← length[A] downto 2
exchange A[1]↔ A[i ]
heap size[A]← heap size[A]− 1
Heapify(A, 1)
I O algoritmo Heapsort executa em tempo O(n lg n)
Heaps e A´rvores Bina´rias 23 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
16
14 10
8 7 9 3
2 4 1
⇒
16
14
108
7 9 3
2
4
1
Heaps e A´rvores Bina´rias 24 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
16
14
108
7 9 3
2
4
1
⇒
1614
10
8
7
9
3
2
4 1
Heaps e A´rvores Bina´rias 25 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
1614
10
8
7
9
3
2
4 1
⇒
161410
8
7
9
3
24 1
Heaps e A´rvores Bina´rias 26 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
8
7
9
3
24 1
⇒
161410
8
7
9
3
24 1
Heaps e A´rvores Bina´rias 27 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
8
7
9
3
24 1
⇒
161410
8
7
9
3
2
4
1
Heaps e A´rvores Bina´rias 28 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
8
7
9
3
2
4
1
⇒
161410
87 9
32
4
1
Heaps e A´rvores Bina´rias 29 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
87 932
4
1
⇒
161410
87 9
3
2
4
1
Heaps e A´rvores Bina´rias 30 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
87 9
3
2
4
1
⇒
161410
87 9
3
2
4
1
Heaps e A´rvores Bina´rias 31 / 59
Heapsort
Algoritmo de Ordenac¸a˜o
Heapsort
Exemplo
161410
87 9
3
2
4
1
⇒
161410
87 9
32
4
1
Heaps e A´rvores Bina´rias 32 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Fila de prioridades
I Uma fila de prioridades e´ uma estrutura de dados para
manter um conjunto dinaˆmico S de elementos, cada um com
um valor associado, chamado de chave.
I As operac¸o˜es sa˜o:
I Insert(S , x): insere um elemento em S
I Maximum(S): retorna o elemento de maior chave de S
I Extract Max(S): extrai o elemento de maior chave de S
I Uma aplicac¸a˜o e´ o escalonamento de tarefas em um
computador de memo´ria compartilhada.
Heaps e A´rvores Bina´rias 33 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Extrair o ma´ximo
Heap Extract Max(A)
if heap size[A] < 1
error(”underflow”)
max ← A[1]
A[1]← A[heap size[A]]
heap size[A]← heap size[A]− 1
Heapify(A, 1)
return max
I O tempo de execuc¸a˜o e´ O(lg n)
Heaps e A´rvores Bina´rias 34 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Inserir novo elemento
1) Expandimos o tamanho do heap introduzindo o novo elemento
2) Navegamos atrave´s da a´rvore ate´ que o elemento atinja a
posic¸a˜o correta para manter a propriedade heap.
Heaps e A´rvores Bina´rias 35 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Inserir novo elemento
Heap Insert(A, key)
heap size[A]← heap size[A] + 1
i ← heap size[A]
while i > 1 & A[Parent(i)] < key
A[i ]← A[Parent(i)]
i ← Parent(i)
A[i ]← key
I O procedimento executa em tempo O(lg n)
Heaps e A´rvores Bina´rias 36 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Exemplo
16
14 10
8 7 9 3
2 4 1
⇒
16
15
14 10
8 7 9 3
2 4 1
Heaps e A´rvores Bina´rias 37 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Exemplo
16
15
14 10
8 7 9 3
2 4 1
⇒
16
15
14 10
8
7
9 3
2 4 1
Heaps e A´rvores Bina´rias 38 / 59
Heapsort
Fila de prioridades
Heap como uma fila de prioridades
Exemplo
16
15
14 10
8
7
9 3
2 4 1
⇒
16
15
14
10
8
7
9 3
2 4 1
Heaps e A´rvores Bina´rias 39 / 59
A´rvores Bina´rias
Suma´rio
Introduc¸a˜o
Heapsort
A´rvores Bina´rias
Heaps e A´rvores Bina´rias 40 / 59
A´rvores Bina´rias
A´rvores Bina´rias de Pesquisa
Introduc¸a˜o
I A´rvores bina´rias de pesquisa sa˜o estruturas de dados que
suportam muitas das operac¸o˜es executadas sobre conjuntos
dinaˆmicos
I Operac¸o˜es: Search, Minimum, Predecessor , Insert e Delete
I As Operac¸o˜es levam tempo proporcional a` altura da a´rvore.
I Para uma a´rvore bina´ria completa de n no´s, tais operac¸o˜es
levam Θ(lg n).
I Todavia, se a a´rvore e´ uma lista de no´s, as operac¸o˜es podem
levar Θ(n) no pior caso.
Heaps e A´rvores Bina´rias 41 / 59
A´rvores Bina´rias
A´rvores Bina´rias de Pesquisa
Introduc¸a˜o
I A altura de a´rvores bina´rias constru´ıdas randomicamente e´
O(lg n), o que garante que as operac¸o˜es executam em Θ(lg n)
passos.
I Na pra´tica, na˜o podemos garantir que as a´rvores sa˜o
constru´ıdas randomicamente.
I Entretanto, existem implementac¸o˜es de a´rvores bina´rias
balanceadas, que garantem uma altura O(lg n) para a a´rvore,
tais como Red-Black Trees, AVL Trees e B-Trees.
Heaps e A´rvores Bina´rias 42 / 59
A´rvores Bina´rias
A´rvores Bina´rias de Pesquisa
O que e´ a´rvore bina´ria de pesquisa?
Toda a´rvore bina´ria que satisfaz a propriedade a´rvore-bina´ria de
pesquisa:
I Seja x um ve´rtice qualquer da a´rvore bina´ria de pesquisa
I Se y e´ um no´ da suba´rvore da esquerda, enta˜o key [y ] ≤ key [x ]
I Se y e´ um no´ da suba´rvore da direita, enta˜o key [y ] ≥ key [x ]
x
≥≤
Heaps e A´rvores Bina´rias 43 / 59
A´rvores Bina´rias
A´rvores Bina´rias de Pesquisa
Exemplos
2
3
5
5
7
8
2
3
5
5
7
8
Heaps e A´rvores Bina´rias 44 / 59
A´rvores Bina´rias
Inorder walk
A´rvores Bina´rias de Pesquisa
Inorder tree walk
A propriedade a´rvore-bina´ria de pesquisa nos permite imprimir
todas as chaves da a´rvore bina´ria em ordem com um simples
algoritmo recursivo.
Inorder Walk(T , x)
if x 6= NIL
Inorder Walk( T , left[x ] )
print(key [x ])
Inorder Walk( T , right[x ] )
A chamada Indorder Walk( T , root[T ] ) e´ executada em tempo
Θ(n), retornando para os exemplos anteriores 2, 3, 5, 5, 7, 8.
Heaps e A´rvores Bina´rias 45 / 59
A´rvores Bina´rias
Buscas
A´rvores Bina´rias de Pesquisa
Busca em uma a´rvore
As operac¸o˜es:
I Search(T , k)
I Minimum(T )
I Maximum(T )
I Predecessor(T , x) e
I Sucessor(T , x)
sa˜o executadas em tempo O(h), onde h e´ a altura da a´rvore T .
Heaps e A´rvores Bina´rias 46 / 59
A´rvores Bina´rias
Buscas
Busca em uma a´rvore
Search
Dados um ponteiro para a raiz T e uma chave k, o procedimento
Search(T ,k) retorna um ponteiro para um objeto com a chave k se
um existe, ou NIL caso contra´rio.
Search(x , k)
if x = NIL or key [x ] = k
return x
if k < key [x ]
Search(left[x ], k)
else
Search(right[x ], k)
Heaps e A´rvores Bina´rias 47 / 59
A´rvores Bina´rias
Buscas
Busca em uma a´rvore
Exemplo
acements
2
3
4
6
7
9
13
15
17
18
20
A busca pela chave 13, segue o caminho 15→ 6→ 7→ 13.
Heaps e A´rvores Bina´rias 48 / 59
A´rvores Bina´rias
Mı´nimo e Ma´ximo
M´ınimo e Ma´ximo
O elemento cuja chave e´ m´ınima pode ser encontrado ao ao
seguirmos a cadeia“left child”a partir da raiz ate´ que NIL seja
encontrado. Para o ma´ximo, o precedimento e´ semelhante.
M´ınimo
Minimum(x)
while left[x ] 6= NIL
x ← left[x ]
return x
Ma´ximo
Maximum(x)
while right[x ] 6= NIL
x ← right[x ]
return x
Heaps e A´rvores Bina´rias 49 / 59
A´rvores Bina´rias
Sucessor e Predecessor
Sucessor e Predecessor
I O sucessor de um no´ x e´ o no´ y com a menor chave key [y ]
que seja maior do que key [x ].
I A estrutura da a´rvore bina´ria nos permite encontrar o sucessor
de um no´ x , sem fazer nenhuma comparac¸a˜o de chaves.
I Se a sub-a´rvore a` direita de x e´ na˜o-vazia, enta˜o o sucessor de
x e´ o elemento m´ınimo desta sub-a´rvore.
I Caso contra´rio, o sucessor de x e´ o ancestral mais pro´ximo de
x cujo filho da esquerda e´ tambe´m um ancestral de x .
Heaps e A´rvores Bina´rias 50 / 59
A´rvores Bina´rias
Sucessor e Predecessor
Sucessor
Successor(x)
if right[x ] 6= NIL
return Minimum(right[x ])
y ← p[x ]
while y 6= NIL & x = right[y ]
x ← y
y ← p[y ]
return y
Heaps e A´rvores Bina´rias 51 / 59
A´rvores Bina´rias
Sucessor e Predecessor
Sucessor
Exemplo
acements
2
3
4
6
7
9
13
15
17
18
20
I O sucessor de 13 e´ 15
Heaps e A´rvores Bina´rias 52 / 59
A´rvores Bina´rias
Inserc¸a˜o de Objetos
Inserc¸a˜o de Objetos
Insert
Insert(T , z)
y ← NIL
x ← root[T ]
while x 6= NIL
y ← x
if key [z ] < key [x ]
x ← left[x ]
else
x ← right[x ]
endif
endwile
Insert (Continuation)
p[z ]← y
if y = NIL
root[T ]← z
else
if key [z ] < key [y ]
left[y ]← z
else
right[y ]← z
endif
endif
Heaps e A´rvores Bina´rias 53 / 59
A´rvores Bina´rias
Inserc¸a˜o de Objetos
Inserc¸a˜o de Objetos
Exemplo
I Inserc¸a˜o de 13
2
5
9
12
13
15
17
18
19Heaps e A´rvores Bina´rias 54 / 59
A´rvores Bina´rias
Delec¸a˜o
Delec¸a˜o
O procedimento de delec¸a˜o de um no´ z consiste em 3 casos.
a) Se z na˜o tem filhos, modificar o pai de z , p[z ], para que este
aponte para NIL.
b) Se z possui apenas um filho, fazemos o pai de z apontar para
o filho de z .
c) Se z possui dois filhos, colocamos no lugar de z o seu
sucessor, o que com certeza na˜o possui filho a` esquerda.
Heaps e A´rvores Bina´rias 55 / 59
A´rvores Bina´rias
Delec¸a˜o
Delec¸a˜o
Caso a: z na˜o possui filhos
3
5
6
7
10
12
13
15
16
18
20
23z
⇒
3
5
6
7
10
12
15
16
18
20
23
Heaps e A´rvores Bina´rias 56 / 59
A´rvores Bina´rias
Delec¸a˜o
Delec¸a˜o
Caso b: z possui um filho
3
5
6
7
10
12
13
15
16
18
20
23
z
⇒
3
5
6
7
10
12
13
15
18
20
23
Heaps e A´rvores Bina´rias 57 / 59
A´rvores Bina´rias
Delec¸a˜o
Delec¸a˜o
Caso c: z possui dois filhos
3
5
6
7
10
12
13
15
16
18
20
23
y
z
⇒ 3
5
6
7
10
12
13
15
16
18
20
23
y
z
Heaps e A´rvores Bina´rias 58 / 59
A´rvores Bina´rias
Delec¸a˜o
Delec¸a˜o
Caso c: z possui dois filhos
3
5
6
7
10
12
13
15
16
18
20
23
y
z
⇒ 3
6
7
10
12
13
15
16
18
20
23
Heaps e A´rvores Bina´rias 59 / 59
A´rvores Bina´rias
Delec¸a˜o
Heaps e A´rvores Bina´rias
I Fim!
I Obrigado pela presenc¸a