Priority Queues

You learned about , and discovered that the queue is a list in which items are processed first in, first out (FIFO). Essentially, this means that data is inserted only at the end of the queue, and data is accessed and removed only from the front of the queue. In accessing the queue’s data, we give precedence to the order in which the data was inserted.

A priority queue is a list whose deletions and access are just like a classic queue but whose insertions are like an ordered array. So we only delete and access data from the front of the priority queue, but when we insert data, we always make sure the data remains sorted in a specific order.

One classic example of where a priority queue is helpful is an application that manages the triage system for a hospital emergency room. In the ER, we don’t treat people strictly in the order in which they arrived. Instead, we treat people in the order of the severity of their symptoms. If someone suddenly arrives with a life-threatening injury, that patient will be placed at the front of the queue, even if the person with the flu had arrived hours earlier.

Let’s say our triage system ranked the severity of a patient’s condition on a scale of 1 to 10, with 10 being the most critical. Our priority queue may look like this:

In determining the next patient to treat, we’ll always select the patient at the front of the priority queue, since that person’s need is the most urgent. In this case, the next patient we’d treat is Patient C.

If a new patient now arrives with a condition severity of 3, we’ll initially place this patient at the appropriate spot within the priority queue. We’ll call this person Patient E:

The priority queue is an example of an abstract data type—one that can be implemented using other, more fundamental, data structures. One straightforward way we can implement a priority queue is by using an ordered array; that is, we use an array and apply the following constraints:

• When we insert data, we ensure we always maintain proper order.
• Data can only be removed from the end of the array. (This will represent the front of the priority queue.)

This approach is straightforward, but now let’s analyze its efficiency.

The priority queue has two primary operations: deletions and insertions.

We saw in Chapter 1, , that deleting from the front of an array is O(N), since we have to shift all the data over to fill the gap created at index 0. However, we’ve cleverly tweaked our implementation so that we consider the end of the array to be the front of the priority queue. This way, we’re always deleting from the end of the array, which is O(1).

With O(1) deletions, our priority queue is in good shape so far. But what about insertions?

You learned that inserting into an ordered array is O(N), since we have to inspect up to all N elements of the array to determine where our new data should go. (And even if we find the correct spot early, we need to then shift all the remaining data over to the right.)

Our array-based priority queue, then, has deletions that are O(1) and insertions that are O(N). If we expect there to be many items in our priority queue, the O(N) insertions may cause some real unwanted drag in our application.

Because of this, computer scientists discovered another data structure that serves as a more efficient foundation for the priority queue. This data structure is the heap.