Jump to content

Brodal queue


xtrm0
 Share

Recommended Posts

A página da wikipedia e uma bela m****, já a tinha lido.

O artigo do acm custa 15$ (e estamos em crise ?). Não sabes algum site que descreva o algoritmo (de graça 😕 )?

Não quero usar a queue para nada, apenas me deparei com ela quando lia esta página (http://en.wikipedia.org/wiki/Heap_%28data_structure%29#Comparison_of_theoretic_bounds_for_variants) e como ja sabia usar duas destas estruturas(binary e pairing) achei estranho ser possível executar todas as operaoes em O(1) (excepto a remocao do minimo). E como conhecimento nunca é demais, pensei: "porque não apreder a implementá-la?".

<Signature goes here>

Link to comment
Share on other sites

Boa noite.

Já comecei a programar a classe BQueue, no entanto ainda tenho um problema:

1-Não consigo implementar a função meld(q1, q2), e por isso nao consigo avancar mais na implementação da queue.

Estou a utilizar a estrutura de dados que o autor referenciou na página 47 (59 do pdf da tese). Decidi começar por esta, pois não consigo compreender como funciona a do capítulo VI (que tem complexidade O(1) para tudo excepto para remover o minimo).

Aqui fica o código que já tenho:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

struct node{
      int minimo;
      int n;
      int rank;
      bool type; //1-true 2-false
      node* parent;
      node* leftmostchild;
      node* nextleft;
};

class BQueue{
     node pts[10000];
     int last; //diz qual foi o ultimo ponto a ser utilizado
     node * root;
public:
      BQueue(){ //done
          root = NULL;
          last=0;
      }
      node findMin(){ //done
          return *root;
      }
      int insert(int nv, int nm){ //é fazer um meld, agora só falta saber como, nm é o numero na array grafo

      }
      node delMin(){
          return *root;       
      }
      void decreaseKey(int e, int nv){
       return;
      }
      void meld(BQueue Q1, BQueue Q2) {
       return;
      }
};





//codigo que apenas tem a ver com o algoritmo de dijkstra, e que se encontra pouco optimizado
struct no{
 vector <int> filhos; //todos os nós para os quais o vertice no nó actual aponta
 vector <int> pesos;  //o peso de cada um dos vertices que liga o no pai
};
int main() {
   int N, A;//N-> numero de nos, A->Numero de arcos
   no grafo[10000];
   BQueue que;
   cin >> N >> A;
   for (int i=0; i<A; i++) { //o input vem com três casas por linha, no seguinte formato: "a b c\n"
   //a->ponto de partida do arco, //b-> ponto de chegada do arco, //c-> peso do arco
       int a,b,c;
       cin >> a >> b >> c;
       grafo[a].filhos.push_back(b);
       grafo[a].pesos.push_back(c);
   }
   //insere todos os elementos na queue, com distancia a no(0) infinita.
   que.insert(0,0); //o no(0) tem distancia 0 do no(0)
   for (int i=1; i<N; i++)
       que.insert(numeric_limits<int>::max(),i); //todos os outros nós têm distancia inf

   //pesquisa o caminho menos pesado, desde o no(0) ate ao no(N-1), utilizando o algoritmo de dijktra
   for (int i=1; i<N; i++) {
       node melhor = que.findMin();
       que.delMin();
       if (melhor.minimo == numeric_limits<int>::max()) break;
       //cajo nao consiga ir para mais nenhum vertice, ou haja algum problema com a queue
       if (melhor.n==N-1) {
           cout << melhor.minimo << endl;
           break;
       }//caso ja tenha chegado ao no pretendido

       for (int j=0; j<grafo[melhor.n].filhos.size(); j++) {
           que.decreaseKey(grafo[melhor.n].filhos[j], melhor.minimo + grafo[melhor.n].pesos[j]);
           //a funcao decrease key é que tem que verificar se o peso é menor ou nao.
       }
   }

   return 0;   
}

<Signature goes here>

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.