When would I use a priority queue?

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?

Solution 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)

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

Solution 3

Scanning through a large collection of statistics to report the top N items - N busiest network connections, N most valuable customers, N largest disk users...

Solution 4

Here is the list: Event-driven simulation: customers in a line, colliding particles

Numerical computation. reducing roundoff error Data compression. Huffman codes which compresses data. Graph searching: Dijkstra's algorithm, Prim's algorithm Number theory: sum of powers Artificial intelligence: A* search Statistics: maintain largest M values in a sequence Operating systems: load balancing, interrupt handling Discrete optimization. bin packing, scheduling Spam filtering. Bayesian spam filter

Solution 5

There are many applications of Priority queue (min/max heap). But if you're looking for classic and famous algorithms Prim's algorithm to find a minimum spanning tree for a weighted undirected graph, for an example, uses priority queue.

View more solutions

Comments

[Mitch Wheat]

when you have priorities and you want to queue them.... C'mon what were you expecting?!?

[Ted Hopp]

Almost any heuristic search (not just Dijkstra); producer-consumer with priority; lots of other things.

[Oleksiy]

How would you use it with a heapsort? And can everyone use the answer pls? You're answering my question, not commenting on it.

[developer747]

Routers use priority queues when managing packet traffic cisco.com/c/en/us/td/docs/ios/12_2/qos/configuration/guide/…