Filas prioritária( Algoritmos e estruturas de dados 1)

filas prioritárias
->estrutura de dados linear
->tipo de dados
    abstracto (ADT) com as seguintes prioridades:
* supostas operações de - inserção( de um novo elemento na fila)
                -remoção do elemento que esta na cabeça  da fila isto é, o elemento maior  prioridade,tipicamente o elemento com maior de chave

API da fila prioritária(PG-Priority Queue)

void insert QP(PQueu *pq,int elemento)
int DelMaxPQ(PQueu*pq)


exemplo: os seguintes n=8, a chegar por esta ordem á fila
5,2,7,3,1,8,6,4



3 Implementações de possíveis PQ:
a)Usar um vector não ordenado
    - quando chega um elemento é colocado no final do vector(custo 1-constante)
    - quando queremos remover o maior elemento temos fazer n comparações para determinar o maior elemento

b)Usar um vector ordenado
- quando chega um novo elemento é feita a fusão ordenada com o vector ordenado já  existente(inserção tem custo linear)
- remoção com custo, constante-1

c)Binary Heap
- implementar uma árvore binária balanceado usando um vector

ex: árvore binária
- estrutura de dados não linear em que casa elemento tem: 0,1, ou 2 filhos
-existe uma só raiz na árvore
-> A árvore binária satisfaz as seguintes condições
   - todos os niveis estão completamente preenchido excepto o ultimo nível que pode estar parcialmente preenchido

-> Para uma Binary Heap
que implemente uma fila prioritária(PQ) sem elementos repetidos, dado qualquer elemento da árvore binária ele tem que ser sempre maior que os seus filhos (0,1, ou 2 filhos)

->nuance de implementação vamos deixar a posição 0 do vector da raiz aparece na posição 1
-> Dado um elemento da posição(índice) k o seu pai esta na posição k/2(divisão inteiro)
->os filhos do elemento de índice k estão nas posições 2*k e 2*k+1

Algoritmo de Pesquisa Binária

Para a implementação da pesquisa binária num vector V de N valores inteiros ordenados de uma forma crescente, adopta-se o seguinte algoritmo:

Função  Pesquisa_Binária(V,N,X)
{   
  1.Inicializar a  pesquisa e inicializar variáveis
        ini=1;
        fim=N;
2. Percorrer o vector para encontrar o elemento
      Do While   ini <= fim
                meio= INT((ini+fim)/2)

                 if  X <V[meio]
                    then fim= meio-1
                 else   if x> V[meio]
                        then ini= meio+1;
                                 else   write("elemento encontrado")
                                       return (meio)
3. Percorreu todo o vector e não encontrou o elemento
  return (0)

Pesquisa Binária

Pesquisa Binária

A estratégia a adoptar neste algoritmo passa por comparar o elemento que procuramos com o valor do elemento armazenado no meio do vector.

* Se esse elemento for menor que o elemento do meio, então conclui-se que, se o elemento estiver presente no  vector , ele estará na primeira parte do mesmo.

* Se o elemento a pesquisar for maior, então estará na segunda parte do vector. Logicamente que se for igual, estará encontrado o elemento do vector e a pesquisa ficará concluída.

*  Se o elemento estiver estiver num das partes do vector, repete-se o procedimento considerando apenas a parte que restou e compara-se o elemento a procurar com o elemento de armazenado no meio dessa parte.

Em suma:
Há 3 tipos de comparações entre o elemento X a pesquisar e o valor v[i] que representa o valor posicionado no meio da estrutura de dados:


     -> Se o X= V[i] então a pesquisa é bem sucedida. A pesquisa termina.

     -> Se o X <V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que procedem V[i], ou seja na primeira metade da lista.

     -> Se X> V[i] então a pesquisa deve prosseguir na sub-lista dos elementos que sucedem V[i], ou seja na segunda metade da lista

Uma ajuda extra

Para ajudar no estudo !!
 Vejam os vídeos do canal ,engloba os algoritmos que abordamos nas aulas 
http://youtu.be/OM8ZHrySAj4

Algoritmo Quick Find

Pseudo-C

função connected(P,Q)
{
   retorna quick_find_ID[P]==quick_find_ID[Q];
}

Função Union(P,Q)
{
    Inicializar a variavel i, , count_comp e vec_size

      Pid=quick_find_ID[P];
      Qid=quick_find_ID[Q];

           Se Pid==Qid
                    retorna
               count_comp--;
    
    For   i=0 to vec_size
            Se quick_find_ID[i]==Pid
                     então
                              quick_find_ID[i]=Qid;
}

Quick Sort (em c)

Quicksort is a very efficient sorting algorithm. It has two phases:
- the partition phase and
-the sort phase,
Most of the work is done in the partition phase. it works out where to divide the work.
The sort phase simply sorts the two smaller problems that are generated in the partition phase.
Complexity: O(n.log n)

void quick_sort(int n, int* v)
{
    if(n<=1)
        return;
    else
    {
        int x=v[0];
        int e=1;
        int d=n-1;

        do
        {
            while(e<n && v[e] <=x) e++;
            while(v[d]>x)d--;
            if(e<d)//faz a troca
            {
                int temp=v[e];
                v[e]=v[d];
                v[d]=temp;
                e++;
                d--;
            }
        }
        while(e<=d); //troca o pivot
        v[0]=v[d];
        v[d]=x;
        //ordena sub vectores restantes
        quick_sort(d,v);
        quick_sort(n-e,&v[e]);
    }

}

Bubble Recrusivo (em C)

O próximo exemplo apresenta uma  implementação recrusica em C do algoritmo bubble sort. Lembrar que o algoritmo recursivo de ordenação posiciona o elemento maior valor e chama, recursivamente, o algoritmo para ordenar o vector vec restante com n-1 elementos

void Bubble_rec(int n, int* vec)
{
    int troca=0;
    int j=0;

    for(j=0; j<n-1; j++)
    {
        if(vec[j]>vec[j+1])
        {
            int temp=vec[j];
            vec[j]=vec[j+1];
            vec[j+1]=temp;
            troca=1;
        }
        if(troca!=0)
            Bubble_rec(n-1,vec);
    }

}