#### Archived

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

# 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 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 on other sites
The easiest way I can think of would be to use a hashtable or sorted vector of queues.

##### 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 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 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 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 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 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 on other sites
"Why search when you can keep it in the class?"

- Huh? I dont follow.

##### Share on other sites
quote:
Original post by GekkoCube
"Why search when you can keep it in the class?"

- Huh? I dont follow.

I think he was confused.

##### Share on other sites
how do you make those horizontal lines to "repost" a quote from somebody else?

##### 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 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 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 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 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]

• ### Forum Statistics

• Total Topics
628348
• Total Posts
2982207

• 10
• 9
• 24
• 11
• 9