Priority queue

Consider a scenario where a traditional queue may not be the best solution, for example, in a hospital's Accident and Emergency department. Using a traditional queue, patients with severe injuries or illnesses may have to wait behind those with less pressing needs, leading to delays in providing necessary care.

To mitigate this, a prioritization system can be implemented. When patients arrive, nurses would assess their condition and place those with more serious needs at the front of the queue, while those with less pressing issues would be moved to the back. This ensures that those who require immediate attention are seen first.

This concept can also be applied to other systems, such as in operating system events. By prioritizing critical issues over less important ones, a priority queue can ensure that the most pressing matters are addressed in a timely manner.

In this topic, you will get to know more about this data structure, its supported operations and applications.

Definition and types

A priority queue is a data structure similar to a regular queue: you can also add elements to and extract elements from it. A priority queue is a special type of queue in which each element is associated with a priority value. Elements are served based on their priority, with higher priority elements being served first. If elements have the same priority, they are served in the order in which they were added to the queue (FIFO). It is a useful data structure for algorithms and systems that need to prioritize certain elements over others.

Priority queues can be classified into two main types: min-priority queue, where the smallest value element has the highest priority, and max-priority queue, where the largest value element has the highest priority. Both types of priority queues store a collection of elements and provide the highest priority element on extraction.

There are several ways to implement a priority queue, including using a linked list, a binary heap, arrays, or a binary search tree. Among these options, using a binary heap is considered to be the most efficient method for implementing it.

Main operations

A priority queue is an abstract data type that supports at least the following operations:

• offer(element) – inserts the specified element into the priority queue;
• peek() – finds and returns the highest priority element from the priority queue without removing it;
• poll() – extracts (i.e. removes from the queue and returns to the program) the highest priority element from the priority queue.

Many programming languages have built-in libraries that provide an implementation of the priority queue data structure.

Since a binary heap is the most efficient data structure for implementing a priority queue, it is naturally the most popular choice for implementing it. So, when a priority queue is implemented using a binary heap, the worst case time complexities of its main operations are as follows:

• offer(element) – $O(\log{n})$ (where $n$ is the size of the queue), as it corresponds to the insert operation in the binary heap. Recall from the topic on binary heaps, that insert means adding the element to the bottom of the heap and then performing a series of comparisons and swaps to re-establish the heap property. This is because it needs to compare the element with its parent node and swap if it has higher priority until it finds its correct position in the heap.
• poll() – $O(\log{n})$ (where $n$ is the size of the queue), as it corresponds to the extract_max (or extract_min in the case of a min-heap) operation in the binary heap. Recall from the topic on binary heaps, that extract_max (or extract_min) means swapping the root node with the last element of the heap, and then repeatedly comparing and swapping the new root node with its children nodes to re-establish the heap property.
• peek() – $O(1)$, because it simply returns the root element of the binary heap, which is the highest priority element.

Example

For the sake of illustration, let's take a look at an example of how you can work with a priority queue.

For simplicity, let's use integer numbers as elements. The priority of an element corresponds to the number itself.

First, let's insert some values into a priority queue:

offer(8)
offer(3)
offer(6)

After the operations are done, the state of the queue can be depicted as follows:

There are three elements ordered according to their priorities. If you perform a few more insertions:

offer(5) // let's call this (element with value 5) as 5′
offer(1)
offer(5) // let's call this (element with value 5) as 5′′
offer(7)

Though there is no distinction in the two elements inserted with the same value $5$, let's call them $5'$ and $5''$, respectively. After these insertions, the priority queue will be in the following state:

All the elements again are ordered according to their priorities. Notice that the elements $5'$ and $5''$ are now sorted in the order of their insertion (FIFO), just like in a regular queue. Now, let's extract a few elements from the queue:

poll() // extracts 8
poll() // extracts 7

After that, you will get the following state:

Let's extract a few more elements from the queue:

poll() // extracts 6
poll() // extracts 5′

After that, you will get the following state:

Now let's extract the remaining elements:

poll() // extracts 5′′
poll() // extracts 3
poll() // extracts 1

After these operations, the priority queue would be empty. And you'll have all of them extracted in the following sorted order:

$8, 7, 6, 5', 5'', 3, 1$

The above priority queue is depicted as an ordered array. However, as mentioned earlier, such an implementation is only one possible variant, which is usually not used due to inefficiency. More efficient implementations are based on the binary heap.

Applications

Priority queues are useful in situations where objects need to be accessed and processed in a specific order of priority. They are commonly used in various situations, including:

• Implementing algorithms: many algorithms require accessing objects in a certain order of priority, such as Dijkstra's Algorithm and Prim's Algorithm in the graph theory. In these cases, a priority queue is used to store objects and facilitate efficient access based on their priorities.

• Data compression: priority queues can be used to implement Huffman Coding, a popular data compression algorithm. The algorithm stores characters of input text and their frequencies in a priority queue. It combines the two least frequent characters repeatedly, resulting in a binary tree used for encoding and decoding input text.

• Sorting: Heap Sort is a sorting algorithm that uses a priority queue, specifically a heap data structure, to sort an array of elements. The algorithm repeatedly selects the maximum element from the heap, places it at the end of the sorted list, and restructures the heap until it is empty.

• In operating systems for:
  • Priority scheduling, where processes must be scheduled based on their priority;
  • Load balancing, where network or application traffic is distributed across multiple servers;
  • Interrupt handling, where a handler is assigned to rectify a situation immediately when a current process is interrupted.

Conclusion

In this topic, you've learned about a special type of queue, namely priority queue, which is commonly used in algorithms and systems that require prioritization. Here's a quick summary of what this topic has covered:

• A priority queue is a data structure that assigns a priority value to each element and allows for quick access to high priority items while maintaining order.
• It is an important data structure for solving problems that involve managing items with varying priorities.
• Priority queue is a widely used concept in computer science, as it allows for efficient prioritization of elements and is commonly utilized in various algorithms and systems.
• There are two main types of priority queues: min-priority queue and max-priority queue.
• One of the main benefits of using a priority queue is its ability to quickly access the item with the highest priority, with a time complexity of $O(1)$. However, the offer() and poll() operations can be slower, with a time complexity of $O(\log{n})$.