Priority Queues

Priority queues are a kind of abstract data type that generalizes 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.

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.

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 built-in 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

class PriorityQueue:
    def __init__(self):
        self.qlist = []
    def insert(self, i, p = 0):
        if len(self.qlist) == 0:
            return self.qlist.append((i, p))
        for x in range(0, len(self.qlist)):
            if self.qlist[x][1] < p:
                return self.qlist.insert(x, (i, p))
        return self.qlist.append((i, p))
    def pop(self):
        if len(self.qlist) == 0:
            return 'Queue empty'
        return self.qlist.pop(0)
    def peek(self):
        return self.qlist[0]
    def __repr__(self):
        return str(self.qlist)

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.

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

>>> pq = PriorityQueue()
>>> pq.insert(('John', 'flu'), 1)
>>> pq.insert(('Sally', 'cut on arm'), 3)
>>> pq
[(('Sally', 'cut on arm'), 3), (('John', 'flu'), 1)]
>>> pq.pop()
(('Sally', 'cut on arm'), 3)
>>> pq.pop()
(('John', 'flu'), 1)

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

>>> pq = PriorityQueue()
>>> pq.insert('Joe', 2)
>>> pq.insert('Polly', 2)
>>> pq.pop()

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

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

>>> 'a' < 'b'
True

So, what will be the output of the following?

1
2
3
4

>>> pq = PriorityQueue()
>>> pq.insert('Hayden', 'd')
>>> pq.insert('Jenna', 'm')
>>> pq.pop()

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

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.

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:

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

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

3. Time-activated Events
   If a program has many events to perform that need to be executed at various 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.

4. Bandwidth 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.