Priority Queue and Mergesort
Is there anybody who can tell me in which situation it will be smart to use Priority Queue instead of Mergesort and vise versa?
Use mergesort when you have a whole bunch of items and you need to sort them.
Use priority queue when you will be adding things to a queue, and then sometimes processing them by priority, and sometimes adding them, and then maybe some more processing, and so on.
Use priority queue when you will be adding things to a queue, and then sometimes processing them by priority, and sometimes adding them, and then maybe some more processing, and so on.
Last edited on
its not 'instead of'
the two things are totally unrelated.
a queue is first in, first out container. The data is not sorted at all. A priority queue sorts the data by its priority, but items of the same priority are still first in first out. A stable sort keeps items in the original order unless they were changed by the sorting process. Stable sorts are a little slower and weirder to write … but that is needed if you sort a single vector or array as a priority queue. Many priority queues avoid this by just being a collection of normal queues, one for each priority, rather that fool with the sorting at all.
mergesort sorts the data. Order of input is not assured even for items of identical value. It has nothing to do with queues.
the two things are totally unrelated.
a queue is first in, first out container. The data is not sorted at all. A priority queue sorts the data by its priority, but items of the same priority are still first in first out. A stable sort keeps items in the original order unless they were changed by the sorting process. Stable sorts are a little slower and weirder to write … but that is needed if you sort a single vector or array as a priority queue. Many priority queues avoid this by just being a collection of normal queues, one for each priority, rather that fool with the sorting at all.
mergesort sorts the data. Order of input is not assured even for items of identical value. It has nothing to do with queues.
In my experience, the only time that items really need to be sorted is when you'll be outputting them in sorted order for human consumption.
We often use sorted containers to facilitate fast lookup of the items. If they are sorted then you can use a binary search. Again, this is for when you want to lookup items quickly.
But now here's a slightly different problem: what if you don't need to lookup random items quickly. What if all you ever need is the first item - the one that compares smallest to all the others. In this case you don't need to know the order of the whole collection, you just need to quickly figure out when one comes first and remove it. That is a priority queue.
We use priority queuing extensively at work. Customers send us "jobs" (the details of the work aren't important). We want to complete each job by a certain time - maybe 2 hours after it was submitted, maybe 2 months. The jobs are processed via priority queue where the completion time is the priority.
We often use sorted containers to facilitate fast lookup of the items. If they are sorted then you can use a binary search. Again, this is for when you want to lookup items quickly.
But now here's a slightly different problem: what if you don't need to lookup random items quickly. What if all you ever need is the first item - the one that compares smallest to all the others. In this case you don't need to know the order of the whole collection, you just need to quickly figure out when one comes first and remove it. That is a priority queue.
We use priority queuing extensively at work. Customers send us "jobs" (the details of the work aren't important). We want to complete each job by a certain time - maybe 2 hours after it was submitted, maybe 2 months. The jobs are processed via priority queue where the completion time is the priority.
Topic archived. No new replies allowed.