#### Archived

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

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

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

1. 1
2. 2
3. 3
4. 4
Rutin
17
5. 5

• 11
• 34
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
631412
• Total Posts
2999939
×