Estruturas de Dados e
Ordenação
Baseado em:
The Algorithm Design Manual
Steven S. Skiena
Introdução (1)



A alteração de uma estrutura de dados
em um programa lento pode mudar
sensivelmente seu tempo de execução.
Esta alteração não muda a corretude do
programa.
É importante projetar os programas
tendo as estruturas de dados como
centro.
Introdução (2)



É importante construir os programas de
forma que implementações alternativas
possam ser experimentadas.
É importante separar os componentes
da estrutura de dados de sua interface.
Esta abstração de dados é importante
para a limpeza, leitura e modificação
dos programas.
Observações (1)



A construção de algoritmos em torno de
estruturas de dados tais como dicionários e
filas de prioridades leva a estruturas limpas e
bons desempenhos.
A escolha errada de uma estrutura de dados
pode ser desastroso para o desempenho.
A escolha da melhor estrutura de dados não
é tão crítica, pois podem existir outras
escolhas que se comportam similarmente.
Observações (2)


A ordenação é uma das partes principais de
um algoritmo. Deveria ser a primeira coisa a
ser feita para buscar eficiência.
A ordenação pode ser usada para ilustrar
muitos paradigmas de projeto de algoritmos.
Técnicas de estruturas de dados, divisão e
conquista, randomização e construção
incremental levam a algoritmos de
ordenação.
Tipos de dados fundamentais


Um tipo de dado abstrato é uma
coleção de operações bem definidas
que podem ser feitas em uma estrutura
particular.
São estas operações que definem o que
a estrutura faz, mas não como ela
funciona.
Containers


É uma estrutura de dados que permite
o armazenamento e a recuperação de
dados independentemente de seu
conteúdo.
As operações fundamentais são:


Put(C,x) – insere o dado x no container C.
Get(C) – recupera o próximo item do
container C. Tipos diferentes de containers
admitem diferentes tipos de recuperação,
baseado na ordem ou posição de inserção.
Containers (2)


A utilidade de containers é maior
quando a quantidade de dados é
limitada e a ordem de recuperação é
pré-definida ou irrelevante.
Tipos de containers:



Pilhas
Filas
Tabelas
Pilhas




LIFO.
Simples de implementar.
É o container correto quando a ordem
de recuperação não importa.
Operações: push (Put) e pop (Get).
Filas




FIFO.
Parece ser a melhor maneira de controlar
tempos de espera.
São mais difíceis de implementar do que
pilhas e são apropriadas apenas em
aplicações em que a ordem é importante.
Operações: enqueue (Put) e dequeue (Get).
Tabelas



Aceitam recuperação pela posição.
As operações de Put e Get aceitam um
índice como argumento.
Tabelas são geralmente implementadas
utilizando arrays.
Implementação de containers



Pode-se usar arrays ou listas ligadas.
A escolha entre uma ou outra depende
do conhecimento da quantidade de
dados a ser armazenada.
Com o uso de arrays, as operações
Put e Get podem ser implementadas em
tempo constante.
Dicionários


São uma forma de container que permite
acesso aos dados armazenados pelo seu
conteúdo.
As principais operações são:



Search(D,k) – Dada uma chave k, retorna um
ponteiro para um elemento em D cujo valor é
k, se existir.
Insert(D,x) – Insere o dado de valor x em D.
Delete(D,x) – Dado um ponteiro para um item
de valor x, remove-o de D.
Implementação

Lista ligada desordenada



Array ordenada




Inserção e remoção em tempo constante.
Consulta atravessa a lista toda.
Consulta por busca binária em tempo O(log n).
Inserção e remoção levam tempo linear.
Árvore de Busca Binária
Tabelas de Hash
Ávores de Busca Binária




Operações sobre dicionário são rápidas.
É uma árvore com raiz na qual cada nó
contém no máximo dois filhos.
Os filhos recebem os rótulos right ou left,
conforme sua posição em relação ao pai.
Os nós são rotulados com as chaves de forma
que todos os nós da subárvore à esquerda de
um nó x tenham valores menores que x e
todos à direita tenham valores maiores que x.
Consulta
BinaryTreeQuery(x,k)
if (x=nil) or (k=key[x])
then return x
if (k < key[x])
then return BinaryTreeQuery(left[x],k)
else return BinaryTreeQuery(right[x],k)

Tempo O(h), h é a altura da árvore.
Inserção



O item a ser inserido deve ser colocado
na última posição em que pode ser
encontrado.
Esta posição é determinada ao fazer-se
uma busca pelo valor a ser inserido.
A inserção propriamente dita leva
tempo constante após a determinação
deste local (que leva tempo O(h)).
Remoção



É mais difícil que a inserção, pois o nó a
ser removido pode não ser uma folha.
A remoção de folhas é fácil, mas a
simples remoção de um nó interno não
permite acesso aos itens abaixo dele.
Uma reestruturação ou rerotulação dos
nós, de forma a levar o item a ser
removido para uma folha, é necessário.
Implementação (1)



Todas as operações levam tempo O(h).
A menor altura possível é O(log n),
quando a árvore está perfeitamente
balanceada.
Ao inserirmos aleatoriamente os dados
em uma árvore, a probabilidade da
árvore resultante ter altura O(log n) é
grande.
Implementação (2)


O pior caso ocorre quando a árvore é
um caminho.
Para evitar o desbalanceamento usa-se
estruturas mais sofisticadas como, por
exemplo, árvores rubro-negras.
Filas de Prioridade (1)




Utilizadas em aplicações onde os itens são
processados em uma ordem particular.
Por exemplo, o escalonamento de tarefas.
As filas de prioridade apresentam vantagem
sobre a ordenação pois as tarefas entram no
sistema em intervalos arbitrários.
É mais caro reordenar do que manter os
dados em uma fila de prioridade.
Filas de Prioridade (2)

As principais operações são:



Insert(Q,x) – inserir o item x na fila Q.
Find_Minimum(Q) ou Find_Maximum(Q) –
retorna um ponteiro para o menor ou maior
valor em Q.
Delete_Minimum(Q) ou Delete_Maximum(Q) –
remove da lista Q o item com menor ou maior
valor.
Implementação (1)




Qualquer uma delas leva tempo O(log n),
representando os dados por uma árvore
de busca binária.
A busca do menor (maior) valor pode ser
feita buscando-se o valor mais à esquerda
(direita) na árvore.
A inserção é feita como na árvore.
A remoção consiste em uma busca seguida
da remoção de um nó da árvore.
Estruturas de Dados
Especializadas (1)


As estruturas vistas mostram uma
representação para um conjunto
desestruturado de dados de forma a
facilitar operações de recuperação.
Existem também estruturas de dados
potentes utilizadas para representar
tipos de objetos mais bem estruturados
tais como pontos no espaço, cadeias e
grafos.
Estruturas de Dados
Especializadas (2)

Para estes dados:


Existe um conjunto de operações básicas
que devem ser feitas repetidamente.
Procuramos estruturas de dados que
executem estas operações eficientemente.
Cadeias (Strings)


Representadas geralmente por arrays
de caracteres, com possivelmente um
caracter especial para designar o fim da
cadeia.
Árvores de sufixos e Arrays de sufixos
são estruturas de dados especiais para
o pré-processamento de cadeias para
tornar a busca de padrões rápida.
Dados Geométricos



Consiste geralmente de coleções de
pontos e regiões.
Regiões no plano são descritas por
polígonos, cujas fronteiras são dadas
por cadeias de segmentos de reta.
Estruturas de dados espaciais, tais
como kd-trees organizam os pontos e
regiões pela localização geométrica de
forma a tornar a busca rápida.
Grafos


Geralmente são representados por
matrizes de adjacência ou por listas de
adjacência.
A escolha da representação é
importante no algoritmo resultante.
Conjuntos

Subconjuntos de itens são geralmente
representados usando dicionários, de
forma a tornar as consultas de
pertinência rápidas.
Ordenação (1)


A ordenação é a base na qual muitos
algoritmos são construídos. Entendendo
a ordenação, tem-se conhecimento para
resolver outros problemas.
Computadores gastam mais tempo
ordenando do que fazendo qualquer
outra coisa. A ordenação aparece em
muitos problemas na prática.
Ordenação (2)


É o problema mais estudado em ciência
da computação.
Muitas das idéias usadas no projeto de
algoritmos aparecem no contexto de
ordenação, tais como divisão e
conquista, estruturas de dados e
algoritmos randomizados.
Aplicações da Ordenação






Busca
Par mais próximo
Unicidade de elementos
Distribuição de freqüência
Seleção
Casco convexo
Busca


Uma busca binária em um dicionário
com os dados ordenados leva tempo
O(log n).
Provavelmente esta seja a mais simples
e importante aplicação da ordenação.
Par mais próximo



Dado um conjunto de n números, como
encontrar o par de números cuja
diferença entre eles seja a menor
possível?
Com os números ordenados a solução é
simples.
Solução em tempo O(n logn) .
Unicidade de elemento



Dado um conjunto de n elementos,
existem elementos duplicados?
Novamente, a melhor solução possível
usa a ordenação.
É um caso particular do problema do
par mais próximo em que a diferença
entre vizinhos é zero.
Distribuição de freqüência

Dado um conjunto de n elementos, qual
elemento ocorre o maior número de
vezes?
Seleção



Qual o k-ésimo maior elemento no
conjunto?
Com os dados ordenados, esta
informação é determinada em tempo
constante.
Em particular, a mediana (o n/2-ésimo
elemento).
Casco convexo (1)



Dado um conjunto de n pontos no plano
cartesiano, qual o polígono convexo de
menor área que contém todos estes
pontos?
Os pontos são ordenadas pelas abscissas
dos pontos.
A partir do ponto de menor abscissa, o
casco é construído inserindo-se os pontos.
Estruturas de Dados


Ordenação por seleção.
Implementação usando um vetor desordenado,
leva:




O(1) para reposicionar o elemento, e
O(n) para localizar o elemento.
Ordenação por seleção leva tempo O(n²).
Se usarmos um heap ou árvore de busca
balanceada o algoritmo leva tempo O(n log n),
heapsort
Inserção incremental



Ordenação por inserção
É um dos exemplos mais simples da
técnica de inserção incremental.
É uma técnica particularmente útil em
algoritmos geométricos.
Divisão e conquista


Ordenação por intercalação
Um problema grande pode ser dividido
em problemas menores que são
resolvidos. A solução de cada um deles
é então combinada para obter-se a
solução do problema inicial.
Randomização




Quicksort
Os pivôs são escolhidos aleatoriamente.
Com esta escolha, o algoritmo tem alta
probabilidade de ser executado em
tempo Q(n log n).
No pior caso é quadrático.
Técnica de Encestamento



Segundo algum critério os dados são
agrupados em cestos (buckets) e os
cestos são tratados individualmente.
Esta idéia esta presente em tabelas de
hash, kd-trees, e em outras estruturas
de dados práticas.
A técnica é boa quando os dados ficam
uniformemente distribuídos entre os
cestos.