[Resolvido] Priority Queue - C++ - Portugal-a-Programar
[Resolvido] Priority Queue
By brunomoniz, March 23, 2006 in C++
brunomoniz 0
Boas.. eu tenho que fazer uma classe Priority Queue derivada de uma classe Queue onde já tenho todos os métodos necessários para uma Queue funcionar.
Eu sei que já existe funções no C++ para implementar isto mas não as posso usar.
O que me está neste momento a "moer" o juizo é como vou ordenar as prioridades na queue... alguém tem algum algoritmo para isto? Ou alguma ideia? Basicamente é fazer um método "ordenar" para ordenar a queue... e é este método que me falta fazer...
Boas, uma priority QUEUE nao e mt diferente duma QUEUE normal, numa QUEUE normal o que acontece é k todos os elementos tem igual prioridade, logo ao inserires um elemento inseres no fim.Numa P QUEUE diferentes elementos vao ter diferentes prioridades, logo precisas de uma funcao que dado um objecto da queue te diga a prioridade dele (de preferencia a prioridade será um numero). Desta forma o algoritmo para inserir numa PQUEUE é meter o objecto no fim e depois ir puxando o gajo (em direccao ao principio) até encontrares um elemento que tenha uma prioridade maior ou igual que ele, e nesse caso pára.
Imagina que tens uma fila de supermercado e que tens 2 tipos de pessoas , "normais" e grávidas. Imagina ainda que neste supermercado tá la a dizer que as gravidas podem passar a frente das pessoas "normais", pronto, o que se tá a passar é que a funcao que devolve a prioridade consoante a pessoa atribui uma prioridade maior a uma gravida do que a uma pessoa nao gravida, logo, se tiveres uma fila com pessoas e xegar uma gravida no fim, ela vai passando a frente das pessoas uma a uma e só para quando atingir o principio da fila ou quando à frente dela estiver outra grávida.
É exactamente o mesmo algoritmo que tens de fazer.
Outra questao que nao posso deixar de salientar é que nao concordo do ponto de vista teorico(ie, boa programacao) que uma PQ derive de uma QUEUE, devia ser o contrário porque uma QUEUE normal é um caso particular de uma PQ onde a funcao de prioridade devolve sempre o mesmo valor independentemente do objecto.
Eu já tenho o algoritmo para ordenar a Queue, tornando-a numa PriorityQueue mas agora estou com um problema... o campo prioridade.
Não estou a ver bem onde vou definir o campo...
Nao estou a ver para que precisas de ordenar a queue... a unica diferenca entre a Q e a PQ é na funcao insere, pois o insere da PQ deve ter um ciclo ( ou mecanismo semelhante ) a puxar o elemento para a sua posicao correcta.
A funcao que retorna a prioridade é o cliente da PQ que define pois ele é que sabe que objectos vai meter na tua QUEUE e como calcular a sua prioridade.. tas a ver?
percebi o que queres dizer mas não estou a ver como o implementar...
eu sei que a diferença está na função insere, ou seja, a função insere da PQ leva mais um parametro para indicar a prioridade do objecto. O meu problema está em definir essa prioridade dentro das classes e como definir uma prioridade para cada objecto da queue...