Home

Rehash ou hashagem dupla

Existem duas funções de Hash:

• Uma para usar normalmente 
• Outra para usar quando há colisões.

           h1( i )=( i mod m ) = C1

           h2 = ( i mod m-1 )+1 = C2  ---} usada quando há colisões

           Para calcular o primeiro indice usa-se C1;

           Para calcular o segundo indice ( se existir colisões) usa-se C1+C2;

           Para calcular o terceiro indice ( se também existir colisões ) usa-se C1+2C2, depois C1+3C2, etc... 

Devemos normalizar  h1( i ) e h2 ( i ) para que o tamanho da tabela seja igual.

 

Nota: ( m ) e ( m-1 ) são primos entre si, para que o resto entre os 2 seja diferente de 0.

Exemplo:

h1( i ) = i mod 7 = C1

h2( i ) = ( i mod 6 ) +1 =C2

• 5     h1 ( 5 ) = 5  ----} 5 está vazio;

• 10   h1 ( 10 ) = 3 ----} 3 está vazio;

• 12   h1 ( 12 ) = 5 ----} 5 está ocupado, logo faz-se h2;

             h2 ( 12 ) =1;

             C1+C2 = 5 + 1 = 6  ----} soma-se o C1 com C2 logo 6 está vazio;

• 19  h1 ( 19 ) = 5 ----} 5 está ocupado logo fazemos o h2;

                 h2 ( 19 ) =2 = C1+C2= 5+2=7  ----} como o rehash é circular vai-se inserir no 0;

                 

                 Nota: Se a posição  0  também estivesse ocupado recorreriamos a C1+2C2 

                ( iria inserir-se no 5+2(2)=9 ---}corresponde ao lugar 2)

Heap-sort :

    Àrvore binária com 3 condições (recursivas)

    Heap:

             -}   abs[A(fe)-A(fd)]<=1                                                          

             -}   node ( a ) > node (fe(a))

                node ( a ) > node (fd(a))

            -} folhas -} mais à esquerda possível (todos os filhos têm de estar o mais à esquerda possivel).

 

            Exemplo:

                                                 

            

            Nota: Esta é uma estrutura mais poderosa para o armazenamento em filas de prioridade.

Inserção de um elemento  

A inserção no grafo faz-se no primeiro lugar disponivel, que é o primeiro lugar o mais à esquerda possivel.

Após a inserção a estrutura não está heapificada, portanto temos de transformá-la novamente num heap.

Caso  a 2ª condição não se verifique :

• comparar o elemento inserido com o seu pai, e se for maior trocar de posição;
• fazé-lo de forma recursiva até que o pai seja maior que o filho;

 

Exemplo:

Eliminição de um elemento:

Elimina-se só a cabeça da àrvore. 

Ao fazermos isto, ficamos com 2 àrvores, logo vamos ter de a reconstituir.

Para implementar  prioridade, a eliminação é sempre feita na cabeça. Caso contrário, não deveriamos utilizar o heap.

Exemplo:

Para eliminar um elemento ( da cabeça ):

eliminar (15)

  

Como se utiliza esta estrutura para fazer ordenação?

Para  fazermos a ordenação, temos de passar por 2 fases:

1ª Fase: Criar um heap

2ª Fase: Eliminar o heap para obtermos a lista ordenada. 

 

Exemplo:

• 1ª fase: criação do heap

{ 15, 2, 0, 7, 10, 9, 5 }

 

 

 

• 2ª fase: eliminação do heap

{ 0, 2, 5, 7, 9, 10, 15 }

 

 

 

Grafos

Um grafo é composto por 2 subconjuntos:

• Vértices
• Arcos

G = { V, A }

 

Para entidades ligadas:

                                                                          

G = { { 1, 2, 3, 4}, { (1, 2) (1, 4) (2, 3) (2, 4)}}

 

Se for um grafo com orientação:

 

G = { { 1, 2, 3, 4}, { (1, 2) (1, 4) (3, 2) (2, 4)}}

Grafo com pesos ( ponderado)

 

Caminho - é uma sequência de arcos ligados para ir de 1 até n.

           

Conexidade dum vértice - quer dizer que a aprtir desse vertice se pode atingir um outro  vértice qualquer

este grafo não é conexo

 

 

Grafo Conexo - é conexo quando podemos atingir qualquer vertice a partir  de qualquer outro vértice.

 

Ciclo - a partir de um vértice podemos encontrar um caminhopara voltar ao mesmo vértice.

 

 Árvore Livre - é um grafo conexo sem ciclo.

 

Exemplos:

 

• Arvore livre

 

• Àrvore não livre, pois tem ciclos.

Sites de interesse: