When would I use a priority queue? [closed]

Question

The only example of using the priority queue I know of, is the Dijkstra's Algorithm (for calculating minimum cost)

In what other situations would it be useful?

Answer 1

Here's a practical example - for a business application:

You're running a hospital and patients are coming in. There's only one doctor on staff. The first man walks in - and he's served immediately. Next, a man with a cold comes in and requires assistance. You add him to the queue and he waits in line for the doctor to become available. Next, a man with an axe in his head comes through the door. He is assigned a higher priority because he has a higher medical liability. So the man with the cold is bumped down in line. Next, someone comes in with breathing problems. So, once again, the man with the cold is bumped down in priority. This is called triaging in the real world - but in this case it's a medical line.

Implementing this in code would use a priority queue and a worker thread (the doctor) to perform work on the consumable / units of work (the patients)

Answer 2

A priority queue based on a heap is partially sorting the input sequence. This has advantages over straight away sorting it when you don't need the whole sequence, as mcdowella gave a few examples for. In particular, if you only need m of the n elements, you have O(m log n) complexity. A second advantage is when you are dynamically adding elements, i.e. when you don't know the whole sequence in advance. With the heap as backing storage, adding another element is faster than inserting it into a sorted sequence.

Further, when you are popping single elements in a sorted order and then discard them (i.e. you don't need the sorted sequence afterwards), using a priority queue gives the reader the right message. It also makes it rather easy to swap different implementations, e.g. one based on a heap or one that sorts the input sequence in advance. This is a question of taste though, you can always achieve the same using any sequence that you then use accordingly, but this only makes the code more difficult to read.