Priority Queue Use Cases and Applications

You might wonder, why learn priority queues or what are the use cases. Besides being a common software engineering interview question, priority queue is a useful data structure and has many use cases and applications, that we’ll review in this chapter.

Let’s do a thought exercise first. Imagine you’re receiving requests from your users and storing them in a a plain-old FIFO queue to be processed by available workers. With a vanilla queue, the orders will be processed in the order in which they arrived.

Now imagine that you want to expedite orders from paid users and process them first over regular customers. A regular queue won’t help you with this because it is first in, first out (FIFO) and has no regard for the priority of its elements. This is where you’d need to use priority queues.

Here are some common applications of priority queues:

• Process or job queue: Operating systems enqueue processes as they are created or woken up from some state of inactivity, placing them at the rear of the queue, but they usually pick the highest priority process in the queue to run next.

• Task lists in general: Task lists, such as project schedules or shopping lists, are often constructed by adding items to the rear of a list as they are thought of, in their order of arrival, but tasks are removed from the list and completed in some specific priority ordering, such as due date or order of importance.

• Dijkstra’s algorithm: When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra’s algorithm, although one also needs the ability to alter the priority of a particular vertex in the priority queue efficiently. If instead, a graph is stored as node objects, and priority-node pairs are inserted into a heap, altering the priority of a particular vertex is not necessary if one tracks visited nodes. Once a node is visited, if it comes up in the heap again (having had a lower priority number associated with it earlier), it is popped-off and ignored.

• Bandwidth management: Priority queuing can be used to manage limited resources such as bandwidth on a transmission line from a network router. In the event of outgoing traffic queuing due to insufficient bandwidth, all other queues can be halted to send the traffic from the highest priority queue upon arrival. This ensures that the prioritized traffic (e.g. Voice) is forwarded with the least delay and the least likelihood of being rejected due to a queue reaching its maximum capacity

• Huffman coding: The two lowest-frequency trees must be obtained periodically in Huffman coding. One way to achieve this is to use a priority queue.