Priority Queues
Priority queues are a kind of abstract data type that generalize the queue. Their principles are exactly the same except that they also include a priority for every value in the queue. When a value is inserted, a priority is assigned to it. The value with the highest priority is always removed first.
You can think of priority queues like a hospital. Treating patients in a First In First Out (FIFO) approach isn't always a good idea because some patients may be in critical condition. So, a patient who has a cough may come in and be assigned a low priority. Then a patient may come in later who has a gunshot wound, and they would be given a high priority and then be treated first.
Priority queues are very important to systems that juggle multiple programs and their execution (like your laptop). They are also very important to networking systems like the Internet because they can help prioritize important data to make sure it gets through faster.
Contents
Minimal Required Functionality
The priority queue has three basic operations.
Function Name* Provided Functionality insert(i, p)
Add value i with priority p pop()
Remove and return the element with the highest priority peek()
Return the element with the highest priority without changing the queue *Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.
Sample Python Implementation Using a List
The following code is an implementation of the priority queue in python. In an efficient implementation, you can expect to get a runtime of O(log n) for insert (by using binary search to find where to put it). However, for simplicity, we'll stay with O(n).
We'll assign priorities using integers (the higher the integer, the higher the priority). Additionally, we'll show the priority in the string representation of the queue to make exercises easier later on.
Note: Python has builtin implementation of a priority queue and a heap.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

Let's take a look at why this is a poor implementation. The insert
function in a heap takes O(log n) because it is a type of binary search tree. In this implementation, however, we have to potentially look through every value in self.qlist
. This means that our implementation is O(n) for insert
.
Practicing With Priority Queues
Let's use our above implementation to handle patients coming into a hospital. As they come in, we can insert the name of the patient, their condition, and a priority.
1 2 3 4 5 6 7 8 9 

So even though we put John
in the queue first, we put Sally
in with a higher priority, so she was processed first by the pop()
function.
Let's do some practice with priority queues:
1) Take a look at the implementation code above, especially lines 7 and 8. What will be the output of the following?
1 2 3 4 

Both values, Joe
and Polly
have the same priority. Who gets processed first?
If you take a look at line 8 in the implementation, you'll see that we are scanning left until we find a value whose priority is less. If we can't find one, then we'll just append it to the list. So, in this implementation, if there are two values that have the same priority, the one that was there first will come out first.
1 2>>> pq.pop() ('Joe', 2)
We could have easily chosen to do it the opposite way, we just would have to change the
<
operation in line 8 to an equality operator=
;
1) In python, you can compare many types of values, not just integers. For example, you can compare strings. In python, the following will hold:
1 2 

So, what will be the output of the following?
1 2 3 4 

As we saw above, in python, you can compare strings. The
'a'
is less than'b'
. So,'b'
would have a higher priority. By that logic,'m'
should have a higher priority than'd'
.
1 2>>> pq.pop() ('Jenna', 'm')
Time Complexity
Although we used an array in our implementation, priority queues are almost always implemented using some sort of heap. So, the priority queue's time complexity using a heap is the most commonly seen.
\[\begin{array} &&\text{Heap Insert O(log n),} &\text{Heap Pop  O(log n),} &\text{Heap Peek  O(1)}\\ \end{array}\]
For insert, we may have to heapify the entire data structure again. So, while the insertion process only takes O(1) time, the heapify process will take O(log n). The same goes for pop. We know where the max priority value is, but remaking the heap still takes O(log n) time. Peek, as with other abstract data type is a constant time operation.
Applications
Priority queues are used in so many different areas, it's impractical to list them all here. The amount of overhead they introduce (the priority) is usually minimal compared to their benefits. Here are a few examples of priority queues in action:
Operating Systems
The operating system in your computer manages which programs execute at what time. Imagine your program queue is full. Suddenly, a new, highly important program needs to run. Your operating system will put it in the queue with a high priority.
Graph Search Algorithms
Many efficient graph search algorithms such as a* search and dijkstra's algorithm use priority queues to know which nodes to explore next. This application also includes corollaries to graph search such as networking.
TimeActivated Events
If a program has many events to perform that need to be executed at varoius times, the program may use a priority queue. The priority will be the timestamp at which to execute the program. Then the queue will be ordered correctly.
Bandwidith Management
Queues are used to handle data flow on the Internet and other networks. However, not all data is equally important. By prioritizing the important data, the network can make sure that it reaches its destination as quickly as possible. Priority queues are often used for this reason.