Aula 16 - OrdMemSecundaria_Selecao por Substituicao

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

intercalação balanceada por meio de Seleção por Substituição
Lívia N. Andrade
Definições
A implementação do método de intercalação balanceada pode ser realizada utilizando filas de prioridades.
As duas fases do método (quebrar o arquivo em blocos ordenados e intercalação) podem ser implementadas de forma eficiente e elegante.
Operação básica para formar blocos ordenados:
Obter o menor dentre os registros presentes na memória interna, e substituí-lo pelo próximo registro da fita de entrada.
Ziviane, cap 4
2
Definições
A implementação ideal para a operação de substituição do menor item de uma fila de prioridades é por meio de um heap.
A operação de substituição corresponde a:
Retirar o menor item da fila de prioridades.
Colocar um novo item no seu lugar.
Reconstituir a propriedade do heap.
Ziviane, cap 4
3
Heap
É uma seqüência de itens com chaves c[1], c[2], . . . , c[n], tal que:
	para todo i = 1, 2, . . . , n/2.
A definição pode ser facilmente visualizada em uma árvore binária completa:
Heap
Árvore binária completa:
Os nós são numerados de 1 a n.
O primeiro nó é chamado raiz.
O nó [ k/2 ] é o pai do nó k, para 1 < k ≤ n.
Os nós 2k e 2k +1 são os filhos à esquerda e à direita do nó k, para 1 ≤ k ≤ [ k/2 ]
 S R O E N A D
1
2
3
4
5
6
7
Heap
As chaves na árvore satisfazem a condição do heap.
A chave em cada nó é maior do que as chaves em seus filhos.
A chave no nó raiz é a maior chave do conjunto.
Uma árvore binária completa pode ser representada por um array:
A representação é extremamente compacta.
Permite caminhar pelos nós da árvore facilmente.
Os filhos de um nó i estão nas posições 
	2i e 2i + 1.
O pai de um nó i está na posição i div 2.
 S R O E N A D
1
2
3
4
5
6
7
S
R
O
D
A
E
N
7
6
5
4
3
2
1
Heap
Na representação do heap em um arranjo, a maior chave está sempre na posição 1 do vetor.
Os algoritmos para implementar as operações sobre o heap operam ao longo de um dos caminhos da árvore.
Um algoritmo elegante para construir o heap foi proposto por Floyd em 1964.
Dado um vetor A[1], A[2], . . . , A[n].
Os itens A[n/2 + 1], A[n/2 + 2], . . . , A[n] formam um heap.
Os itens de A[4] a A[7] formam um heap.
O heap é estendido para a esquerda (Esq = 3), englobando o item A[3], pai dos itens A[6] e A[7].
A condição de heap é violada:
O heap é refeito trocando os itens D e S.
O heap é estendido para a esquerda (Esq = 2), englobando o item A[2], pai dos itens A[4] e A[5].
A condição do heap não é violada.
O heap é estendido para a esquerda (Esq = 1), englobando o item A[1], pai dos itens A[2] e A[3].
A condição de heap é violada:
O heap é refeito trocando os itens S e O, encerrando o processo.
Intercalação Balanceada 
por meio de Seleção por Substituição
10 15 2 1 
 1 2 3 4
compara [2] com [4]
troca as posições
Exemplo de reconstituição da propriedade do heap:
Intercalação Balanceada 
por meio de Seleção por Substituição
10 1 2 15
 1 2 3 4
Exemplo de reconstituição da propriedade do heap:
Intercalação Balanceada 
por meio de Seleção por Substituição
10 1 2 15
 1 2 3 4
compara [1] com [2]
troca as posições
Exemplo de reconstituição da propriedade do heap:
Intercalação Balanceada 
por meio de Seleção por Substituição
1 10 2 15
 1 2 3 4
Exemplo de reconstituição da propriedade do heap:
Algoritmo:
1. Inserir m elementos do arquivo na fila de prioridades.
2. Substituir o menor item da fila de prioridades pelo próximo item do arquivo.
3. Se o próximo item é menor do que o que saiu, então:
	• Considere-o membro do próximo bloco.
	• Trate-o como sendo maior do que todos os itens do bloco corrente.
4. Se um item marcado vai para o topo da fila de prioridades então:
• O bloco corrente é encerrado.
• Um novo bloco ordenado é iniciado.
Intercalação Balanceada 
por meio de Seleção por Substituição
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
heap
Intercalação Balanceada 
por meio de Seleção por Substituição
memória = 3
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
A condição de heap é violada?
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
Substituir o menor item pelo próximo item do arquivo
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
T
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I
entra
Verificar se este item é menor do que o item que saiu
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
T
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I
entra
E < I
Considere-o membro do próximo bloco, tratando-o como maior do que todos os itens do bloco corrente
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
E*
N
T
R
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I
entra
A condição de heap é violada?
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I 
entra
Substituir o menor item pelo próximo item do arquivo
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N 
entra
Verificar se este item é menor do que o item que saiu.
A condição de heap é violada?
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
C*
E*
T
A
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R 
entra
Retirei o menor item (R), substitui por um elemento menor (C), que deve ser tratado como o maior de todos.
A condição de heap foi violada...
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R 
entra
Os itens foram trocados de lugar e a condição da heap não está mais violada
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
A*
E*
C*
L
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
entra
Retirei o menor item (T), substitui por um elemento menor (A), que deve ser tratado como o maior de todos.
Refazer a condição de heap
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
A*
E*
C*
L
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
entra
Um item marcado foi para o topo da fila de prioridades, então:
 O bloco corrente é encerrado
 Um novo bloco ordenado é iniciado.
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
A*
E*
C*
L
L*
E*
C*
A
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
entra
Retirei o menor item (A*), substitui por um elemento maior (L), que deve ser tratado como o item anterior, pois fará parte do mesmo bloco.
Refazer a condição de heap
A
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
A*
E*
C*
L
E*
L*
C*
A
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
entra
Refazer a condição de heap
A
Exemplo:
1ª Fase: blocos ordenados
I N T E R C A L A C A O B A L A N C E A D A
I
N
T
E
N
E*
T
R
R
E*
T
C
T
E*
C*
A
A*
E*
C*
L
C*
L*
E*
A
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
entra
Selecionar o menor item e Substituir pelo próximo item do arquivo ...
A
Primeira passada sobre o arquivo exemplo.
Os asteriscos indicam quais chaves pertencem
a blocos diferentes.
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
2ª Fase: intercalar os blocos ordenados obtidos na primeira fase
 Operação básica: 
 obter o menor item dentre os ainda não retirados dos f blocos a serem intercalados.
Algoritmo:
• Monte uma fila de prioridades de tamanho m.
• A partir de cada uma das m entradas:
– Substitua o item no topo da fila de prioridades pelo próximo item do mesmo bloco do item que está sendo substituído.
– Imprima em outra fita o elemento substituído.
Intercalação Balanceada 
por meio de Seleção por Substituição
2ª Fase: intercalar os blocos ordenados 
obtidos na primeira fase
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
A
A
I
A
Fita 4
Retirei o menor item (A), substitui pelo próximo item do mesmo bloco do item que está sendo substituído (A).
entra
2ª Fase: intercalar os blocos ordenados 
obtidos na primeira fase
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
A
A
I
A
A
A
I
B
Fita 4
Retirei o menor item (A), substitui pelo próximo item do mesmo bloco do item que está sendo substituído (A).
entra
A 
2ª Fase: intercalar os blocos ordenados 
obtidos na primeira fase
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
A
A
I
A
A
A
I
B
A
B
I
C
Fita 4
Retirei o menor item (A), substitui pelo próximo item do mesmo bloco do item que está sendo substituído (A).
entra
A A 
2ª Fase: intercalar os blocos ordenados 
obtidos na primeira fase
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
A
A
I
A
A
A
I
B
A
B
I
C
B
C
I
C
Fita 4
Retirei o menor item (A), substitui pelo próximo item do mesmo bloco do item que está sendo substituído (A).
entra
A A A 
2ª Fase: intercalar os blocos ordenados 
obtidos na primeira fase
Intercalação Balanceada 
por meio de Seleção por Substituição
Fita 1
Fita 2
Fita 3
I N R T 
A C E L
A A B C L O
A A C E N
A A D
Fita 4
A A A C C E I L L N O R T 
Usando os dados do Exercício 31, mostre como seria a ordenação considerando a implementação por
meio da seleção por substituição usando um heap.
31) Mostre os passos para a ordenação externa dos número inteiros abaixo.
 Arquivo com 53 registros: 13 45 67 23 89 98 65 43 21 12 12 55 66 99 43 32 37 59 61 62 11 5 4 7 8 90 10 20 60 40 30 2 3 6 8 98 76 62 23 26 28 13 8 9 0 21 19 18 27 25 71 73 37
Memória interna para 5 registros
8 unidades de fita (intercalação-de-4-caminhos)
Exercício 33 da lista
Bibliografia consultada
Livro:
Projeto de algoritmos com implementações em PASCAL e C – Nivio Ziviani