Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

GekkoCube

priority queue implementation?

This topic is 5405 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

how many ways can you implement a priority queue? i know of one method, using a heap, thats because of all the literature that uses this - im guessing this is a standard way. i also understand that you can use a vector to implement a priority queue. this part confuses me. is there sample code anywhere?

Share this post


Link to post
Share on other sites
Advertisement
You can find a lot of good information by going to google and searching for whatever your heart desires.

Googling for "priority queue" turns up this interesting document for example, among others:

http://www.leekillough.com/heaps/papers/p157-ronngren.pdf

Share this post


Link to post
Share on other sites
hmm, i will use a heap (min heap).
but before i start, i am unclear as to where the distinction is between a priority queue and a min/max heap.

my data structures texbook suggests making a priority queue class that is abstract, and just allow another class to inherit from it.

im wondering if its a bad design to implement a min heap to make a priority queue in one class.

i guess my original question still stands...how is the priority and the heap related??

Share this post


Link to post
Share on other sites
As far as I know, a priority queue simply specifies valid operations (add item, remove highest priority item).

A heap is a concrete implementation of a binary tree that happens to support a priority queue''s operations very efficiently.

You could make a priority queue with a vector, but it wouldn''t be as efficient. For example, you could re-sort the vector every time an item is added, by order of prioriy, and then you know that if you remove back()/front() (depending on if you sorted ascending/descending), you are getting the highest priority item.

Share this post


Link to post
Share on other sites
so essentially a priority queue is just a name so-to-speak.
and the real work-horse of any priority queue is the data structure or ADT used to create a priority queue. - correct?

now i can organize this a little more in my head.
im thinking the following:

A base class called PriorityQueue, which has pure virtual functions Insert and Delete.

A derived class called MinHeap that inherits from PriorityQueue.

Then i basically use the priority queue like this:


PriorityQueue *PQ = new MinHeap();


im guessting this makes the most sense.

Share this post


Link to post
Share on other sites

Sounds reasonable. You may want to look into the Strategy and Adapter design patterns for insight into how exactly to structure your classes.

Share this post


Link to post
Share on other sites
well, i foresee one problem or obstacle i should say...

in a min heap, i know that the minimum key is the root.
but what about the rest of the tree, is it sorted???
do i sort the entire tree after every insertion?

second, is there pseudocode to sort a tree for the max/min key in the tree? because my data structures textbook sure doesnt offer any.

Share this post


Link to post
Share on other sites
Why search when you can keep it in the class?

STL provides a priority queue implementation, named priority_queue oddly enough!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!