Archived

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

GekkoCube

priority queue implementation?

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
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
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
well,, going back to the whole priority queue & heap thing...

I was wondering if I should implement a heap that is pointer-based or array-based.

what would be the benefits and disadvantages of each?

Share this post


Link to post
Share on other sites
ok, i made up my mind...im going to write a heap that is represented by an array.

but i still have a question regarding even this!

Would it be quite alright with respect to speed and efficiency if i used a dynamically resizeable array, like a vector???

Share this post


Link to post
Share on other sites
quote:
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.

I was saying you don''t need to search, you can just keep track of the min/max as you insert it into your class.

Share this post


Link to post
Share on other sites
you are saying that the min/max does not need to be at the top, or in my array-based case, at index 0?

i dont think this will work. i COULD leave everything unsorted and simply remove the element with the smallest/largest key.

but that would still mean sorting it at some point in time so that if a new element is inserted it''s key must be checked with others.

Share this post


Link to post
Share on other sites
I think what antareus was saying is that if you sort your tree, then you don't have to search at all because the highest priority item will always be in the same place.

[edited by - Martel on September 4, 2003 12:58:33 AM]

Share this post


Link to post
Share on other sites