• Advertisement
Sign in to follow this  

Queue q

This topic is 4788 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hiya, I asked in the AI forum about what kinda list to use for A* algorithm and was told to use a priority queue. I have a few questions about this. (the ppl in the AI forum are slow to respond sometimes hehe) 1. What is the difference between a queue and PRIORITY Queue?? 2. Since I need to sort the queue, is it still a queue... since it won't really be FIFO.

Share this post


Link to post
Share on other sites
Advertisement
A priority queue isn't FIFO, it is sorted by the priority you give the data. In C++ in the STL, they use a -edit- vector as the underlying structure.

Queue works like a line, FIFO. Priority queue doesn't matter about what was first in, the first out is the one with the highest priority (-edit- What you use for the Compare function is what determines highest priority).

SGI's info on the priority queue here

-edit- My mistake, SGI's p-queue uses a vector, not a rb-tree.

Share this post


Link to post
Share on other sites
Can you explain a bit about this Red-Black tree structure? I've heard of it, but never have had to deal with it before. Guess I'll look around.

Share this post


Link to post
Share on other sites
Priority-queue
wiki
Also read about heaps, because that is a way to make a priority queue.


(For RB-Trees)
Googling is probably you quickest bet, it is well known and documented.

A java version of how it works
here

wiki for RB-tree

Share this post


Link to post
Share on other sites
a priority queue is definately not a FIFO ... but it's a queue in the sense that items are added through one end and pulled out through the other (as opposed to a stack where the are (logically) pushed in and pulled out through the same opening.

A priority is RELATED to a queue because each item in it WITH THE SAME PRIORITY should act as if it is in a queue (there are no line jumpers allowed between items of equal priority).

So here's a Queue

ENTRY POINT - ITEM 4 - ITEM 3 - ITEM 2 - ITEM 1 - EXIT POINT

Here's a Priority Queue (letter represents an item's priority, number it's insertion order)

ENTRY POINT
C ENTRY POINT - ITEM C10 - ITEM C7 - ITEM C5 - ITEM C4
B ENTRY POINT - ITEM B11 - ITEM B6 - ITEM B1
A ENTRY POINT - ITEM A9 - ITEM A8 - ITEM A3 - ITEM A2
- EXIT POINT

I hope the way I drew that shows ok ... it's meant to be both 3 seperate lines (queues) and the meta / overall queue ...

the orders of the individual queues are (10,7,5,4) (11,6,1) (9,8,3,2) [notice these ARE in normal FIFO order] and the current order of the meta queue is (10,7,5,4,11,6,1,9,8,3,2) [pririty order first, FIFO second]

Share this post


Link to post
Share on other sites
I am very confused. Apparently I should read up on heaps as well to properly use the priority queue... correct?
Also, I need to get the smallest element, not the largest. Is this what the priority queue's .top() method returns? I have seen an websites that it returns the largest element, while others say smallest.
If I want to store structs in the queue, what must I do for the queue to know what to prioritize? Should I override < operator?
Finally, do I need to write a sorting routine for these things at all, or do they sort themselves everytime I call .push()?
Ah, so many questions. haha

If anyone can write some basic priority queue code in which the queue contains structs, that would be beyond great.

Share this post


Link to post
Share on other sites
You don't need to really know how heaps work to use a priority queue. The basic thing to keep in mind is that the top of the priority queue is either the max or min value you've pushed in, depending on how you specify the sorting function.

Overriding operator<() is probably the easiest way to work with a priority queue, but you can work with stand alone functions if that's what you want. Example:


#include <vector>
#include <queue>
#include <iostream>

struct SomeStruct {
int x;
int y;
};

bool compare_x_lessthan(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x < rhs.x;
}

bool compare_x_greaterthan(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x > rhs.x;
}


int main(int, char **) {
typedef std::priority_queue<SomeStruct, std::vector<SomeStruct>, bool (*)(const SomeStruct &, const SomeStruct &)> MyPriorityQueue;

MyPriorityQueue queue_1(&compare_x_lessthan);
MyPriorityQueue queue_2(&compare_x_greaterthan);

SomeStruct some_structs[] = { { 0, 0}, {-1, -1}, {1, 1}, {0, 2}, {5, - 3} };

queue_1.push(some_structs[0]);
queue_1.push(some_structs[1]);
queue_1.push(some_structs[2]);
queue_1.push(some_structs[3]);
queue_1.push(some_structs[4]);

std::cout << "less than priority queue:" << std::endl;
while (!queue_1.empty()) {
std::cout << queue_1.top().x << "," << queue_1.top().y << std::endl;
queue_1.pop();
}

queue_2.push(some_structs[0]);
queue_2.push(some_structs[1]);
queue_2.push(some_structs[2]);
queue_2.push(some_structs[3]);
queue_2.push(some_structs[4]);

std::cout << "greater than priority queue:" << std::endl;
while (!queue_2.empty()) {
std::cout << queue_2.top().x << "," << queue_2.top().y << std::endl;
queue_2.pop();
}


return 0;
}


In this case MyPriorityQueue stores SomeStructs, is implemented in terms of std::vector, and uses function pointers to determine the order of elements. When I create the priority queues, I pass which function

Share this post


Link to post
Share on other sites
SiCrane and everyone else: THANK YOU!!!!!!!!!!!!!!! I have read up on heaps, and those have branched off into more things which I now am familiar with. So thank you very much for the links and info!
I have one question for SiCrane tho, why the typedef? I used it, but I'm not sure why you did it like that. Is there a way you could have told the priority_queue what function to use in the declaration??

actually, I do have a problem. I am getting an error on this code:
#ifndef EG_GHOST
#define EG_GHOST

#include <queue>
#include <vector>
#include <windows.h>
using namespace std;

struct sLocation
{
int posX;
int posY;
int sum;
int totalDistance;
int heuristic;
};

typedef priority_queue<sLocation, vector<sLocation>, bool (*)(const sLocation &s1, const sLocation &s2)> PriorityQueue;

class Ghost
{
public:
Ghost(CHAR_INFO mapIn);
void SetGoal(int x, int y); //Sets the goal position
void SetStart(int x, int y); //Sets the starting point position
bool FindPaths();
private:
CHAR_INFO map;

sLocation *goalNode;
sLocation *startNode;
vector<sLocation> closedNodes; //Priority Queue to hold closed nodes
PriorityQueue openNodes(&CompareSumLessThan); //Priority Queue to hold open nodes
int index; //Counter for nodes

//Methods
void SetHeuristic(sLocation *current, sLocation goal);
void SetDistance(sLocation *node);

bool CompareSumLessThan(const sLocation &s1, const sLocation &s2);
};

#endif


The error has a prob with the PriorityQueue openNodes(&CompareSumLessThan); line at the '&'. I am missing something here...
PS. This class is not finished. So don't worry about unfinished business other than the priority_queue set up.

[Edited by - fooman_69 on January 8, 2005 1:23:27 PM]

Share this post


Link to post
Share on other sites
I think the error you are getting is because you are calling CompareSumLessThan before you declare it 7 lines later.

move "bool CompareSumLessThan(const sLocation &s1, const sLocation &s2);" above the line "PriorityQueue openNodes(&CompareSumLessThan);" and it should fix that problem. Make sure you actually code the CompareSumLess function as well.
You probably don't need that function as part of that class as well because I don't think it has to do with your Ghost class specifically.

Good luck.

Share this post


Link to post
Share on other sites
No luck. That still gives me an error. "Sytax error: '&'" right at that same line!! ARG!!
I have noticed something tho. When I compiled SiCrane's code and let the cursor hover about his queue_1 and queue_2, the intellisense does not show what mine does. When I let mine hover above openNodes, it shows "... openNodes(void)". There is not supposed to be a (void) there. Why is this??

Share this post


Link to post
Share on other sites
What is your code for CompareLessThan?

It seems really strange that your code doesn't work.

Share this post


Link to post
Share on other sites
I'm not at home so I am going to see if I remeber EXACTLY what my code is (its pretty basic though).
bool CompareSumLessThan(const sLocation &s1, const sLocation &s2)
{
return s1.sum > s2.sum;
}


That is defined in my .cpp file accompanying the header of course.
Thanks for any help.

Share this post


Link to post
Share on other sites
I used a typedef because I was declaring two queues of the same type and I didn't want to type the whole thing out twice.

The problem with your PriorityQueue openNodes(&CompareSumLessThan); line is that you're trying to pass a parameter to the constructor during member variable declaration when you need to be doing that during the constructor for the class.

If you want to use a free standing function to control the order, then you need to wait until the object is constructed to declare the sorter. Otherwise, you can overload operator<() to specify sort order on your class, provide a template specialization for std::less, or declare a function object class that overloads operator(). Example of the last guy:

#include <vector>
#include <queue>
#include <iostream>

struct SomeStruct {
int x;
int y;
};

struct CompareXLessThan {
bool operator()(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x < rhs.x;
}
};

struct CompareXGreaterThan {
bool operator()(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x > rhs.x;
}
};


int main(int, char **) {
std::priority_queue<SomeStruct, std::vector<SomeStruct>, CompareXLessThan> queue_1;
std::priority_queue<SomeStruct, std::vector<SomeStruct>, CompareXGreaterThan> queue_2;

SomeStruct some_structs[] = { { 0, 0}, {-1, -1}, {1, 1}, {0, 2}, {5, - 3} };

queue_1.push(some_structs[0]);
queue_1.push(some_structs[1]);
queue_1.push(some_structs[2]);
queue_1.push(some_structs[3]);
queue_1.push(some_structs[4]);

std::cout << "less than priority queue:" << std::endl;
while (!queue_1.empty()) {
std::cout << queue_1.top().x << "," << queue_1.top().y << std::endl;
queue_1.pop();
}

queue_2.push(some_structs[0]);
queue_2.push(some_structs[1]);
queue_2.push(some_structs[2]);
queue_2.push(some_structs[3]);
queue_2.push(some_structs[4]);

std::cout << "greater than priority queue:" << std::endl;
while (!queue_2.empty()) {
std::cout << queue_2.top().x << "," << queue_2.top().y << std::endl;
queue_2.pop();
}

return 0;
}



Share this post


Link to post
Share on other sites
haha im sorry if you guys are starting to hate me. I had a feeling it had something to do with the object not being created yet, but I didn't know how to deal with this. SiCrane, once again I have another question. I know about operator overloading, but I have never had to overload the ()operator in my studies in college. What is the point of this?? And why put it in a struct?

Share this post


Link to post
Share on other sites
Well, I put it in a struct because I'm sufficiently lazy that I didn't want to declare it as a class and type out "public".

When you overload operator() on a class/struct, you turn the class into a function object: something that you can use like a function, even if it isn't really a function. Using my last code blurb as an example, I can do this:

CompareXLessThan comparer; // make a CompareXLessThan object
SomeStruct a, b;

bool ret_val = comparer(a, b);

If you didn't see the first line, you would probably assume that comparer is a function, but it's actually an object.

Function objects are one of the building blocks of the C++ standard library. For example: std::less<> is actually a function object. In the case of the priority_queue class, by using a function object instead of a function pointer, the desired behaviour gets encoded into the type, so you don't need to pass what function it uses in the constructor; it gets made part of the declaration.

Share this post


Link to post
Share on other sites
Thank you very much for your help. Everything seems to be working well, but I have to test quite a bit more to know for sure. Anyways, is there a way to iterate through this priority_queue of mine?? I need to check nodes against other's to see if they are in the list already.

Share this post


Link to post
Share on other sites
The std::priority_queue class can't be iterated through, and if you could, the heap order doesn't allow for efficient find operations, so depending on your usage, trying to use a priority_queue and searching through it may actually be less efficient than using a std::set.

If linear search time doesn't bother you, what you can do is take a container like std::vector or std::deque and manually use std::make_heap(), std::push_heap() and std::pop_heap() on the container. An example of doing that can be found on msdn here.

Share this post


Link to post
Share on other sites
I have never used a set before, but it seems easy enough. From what I can see, a set will allow me to search for an element and it will return end() if it has not found it. It will allow me to order it as well correct?? A heap seems like it will take a bit longer to work with. I may be able to work with a priority_queue as easily.

Too many list options!!

Share this post


Link to post
Share on other sites
If you are using the priority_queue for A*, then it shouldn't matter about checking to see if something is already in there. You just grab the smallest values, and if you update a node, it will be updated to a smaller value, so just insert it again with a smaller value. Because you won't reach the larger version of it.

Share this post


Link to post
Share on other sites
Quote:
Original post by nprz
If you are using the priority_queue for A*, then it shouldn't matter about checking to see if something is already in there. You just grab the smallest values, and if you update a node, it will be updated to a smaller value, so just insert it again with a smaller value. Because you won't reach the larger version of it.


How come in each of the tutorials I read, they say that I should check to see if the node I am checking is already on the open list??

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement