Understanding Priority Queue, With Examples


There are many kinds of queue structures in programming, each with its own advantages andapplications. One of the most fundamental types is the priority queue. This kind of queue departs from the typical conventions of an ordinary queue but this behavior is desirable in certain scenarios. In this article, we re going to look at how priority queues work, the different ways we can implement them, and best practices.

What is Priority Queue?

Typical queues, such as linear orcircular queues, follow the First-In-First-Out (FIFO) principle. This means that the first element to be inserted will be the first to be removed. This logic is found in many real-life queues, such as people queuing for a burger stand or theme park ride, or waiting in a call list for a call center. However, this type of queue isn t applicable to some situations. Think about the emergency room at a hospital, loyalty customers of a business, or prioritized baggage at an airport. In these cases, there is still a queue present, but the order in which people leave the queue depends on their priority. As such, a priority queue is a much more appropriate structure to use here.

When implementing a priority queue, the elements are accessed in order of their priority, with the highest-priority elements being dealt with first. Generally, the priority is predefined before execution.

Priority Queue Operations

Priority queues use many of the same operations as other queues these include insertion, deletion, and peek (retrieves the highest-priority element). Since a priority queue doesn t obey the FIFO principle, elements are inserted or removed depending on their priority. We can also use size and isEmpty with priority queues, to check the queue size and status.

How Are Priority Queues Used?

Similar to other queues, there are many ways to implement a priority queue. Generally, you can use anarray, a linked list, or a binary heap. We re going to cover each of these briefly.

Array-based priority queues

One of the simplest ways to use a priority queue is with an array. The following code in Python shows an example of this.

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def insert(self, item, priority):
        self.queue.append((item, priority))

    def delete(self):
        if self.is_empty():
            return None
        highest_priority = self.queue[0][1]
        highest_priority_index = 0
        for i in range(1, len(self.queue)):
            if self.queue[i][1] 

Explanation of code

First, we declare the PriorityQueue class, and the __init__ method, which initializes the queue. Then, we define the insert method, which takes the item argument and the priority argument, which is used to assign a priority value to the element.

The delete method is defined after this, which removes the element with the highest priority. We then assign the highest priority to the first element, but then compare this with the other elements. The elements are then reordered according to priority, and the highest-priority element is removed via the pop method.

Similarly, the peek method iterates over the list and returns the item with the highest priority. After that, the isEmpty and size methods are defined.

We finish by creating a queue with 3 elements, or tasks , with their priorities. The size and highest-priority element are printed, then each task is printed as it s processed and deleted. The results can be seen in the image.

Priority Queue
A priority queue is implemented using ann array.

History-Computer.com

Linked list-based priority queue

Another way to implement a priority queue is by using a linked list. This is similar to an array but uses pointers and nodes, and can be dynamically resized. For example, consider this code:

class Node:
    def __init__(self, item, priority):
        self.item = item
        self.priority = priority
        self.next = None

class PriorityQueue:
    def __init__(self):
        self.head = None

    def insert(self, item, priority):
        new_node = Node(item, priority)

        if self.head is None or priority 

Explanation of code

Most of the logic here is the same, but we define the methods differently. We must declare the Node class to represent each element. The delete method is relatively simple here, but the insert method is more complicated than before. This is because we can simply update the front pointer to the next node to remove an element, butlinked listsdon t have random access to elements. Therefore, they must be inserted more thoughtfully.

If the priority of the inserted element is lower than the head node, then we must traverse the list and compare it with each element to find the correct position. The element is inserted by assigning the new node as the next node of the current node. The operations used with this type of queue follow the same syntax, so for brevity s sake, they won t be included here.

Binary heap-based priority queue

This implementation is preferred a lot of the time, as it often gives better performance. This is because they re a tree structure with the heap property. This can be done with either a min heap or a max heap. In the former, each parent node is equal to or less than the values of its child nodes. In the latter, the reverse is true. As such, these are efficient methods for handling priority, because we can guarantee the root node has the highest priority. The following code demonstrates this method.

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.size = 0

    def parent_index(self, index):
        return (index - 1) // 2

    def left_child_index(self, index):
        return 2 * index + 1

    def right_child_index(self, index):
        return 2 * index + 2

    def swap(self, index1, index2):
        self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

    def heapify_up(self, index):
        while index > 0 and self.heap[index] 

Explanation of code

This code block is quite long, so let s break it down. We declare the class as usual and initialize it. An empty list, heap , is created, with an initial size of 0. The parent_index method is defined, which returns the parent node index. This is calculated using division.

After this, we define the left_child_index and right_child_index . These are used to maintain the tree structure, which allows for efficient element access. These are calculated using 2 * index + 1 and 2 * index + 2 respectively. Swap is then defined, which is used to swap elements. This is done by assigning tuples, which are collections of values.

Next, heapify_up is defined, which is used to create the binary heap structure, by moving the necessary elements. Whether the current element violates the heap property or not is checked by using thewhile loop, and this is swapped with the parent loop if necessary. If this is done, the current index is updated to the parent index.

The next method to be defined is heapify_down . This is used after removing an element to restore the heap property. The left and right child indices are calculated, and their priority is checked. If necessary, the element is moved down the heap and swapped with the smallest child element. This is repeated as needed.

Following this, we define the insert and delete methods. When inserting, we must increment the queue size, and call heapify_up to move the inserted item. Likewise, when deleting an element, we must decrement the queue size before removing the element, to ensure the size is accurate. We then use heapify_down to restore the heap property.

Lastly, we define the peek and is_empty methods, which are used to check the highest-priority element and whether the queue is empty or not.

Other Types of Priority Queues

While these are the most common ways to work with priority queues, there are other methods. These include a d-ary heap, which is like a binary heap, except there can be more than 2 child nodes to each parent node. Another type is thebinary searchtree. This is also similar to a binary heap, but each node has a key value, where the key values of the left tree are less than the right tree. To insert and remove elements in a binary search tree, the tree is traversed recursively to find the correct position. You can also customize your priority queue to make use of specific criteria, instead of simpler lower and higher priority values.

Wrapping Up

Priority queues are extremely usefuldata structuresfor organizing the order in which elements or tasks are processed. They can be implemented with a variety of methods, such as arrays, linked lists, binary heaps, or binary search trees. Choosing the correct implementation for your project is important, to ensure optimal performance and efficiency of operations.

Leave a Comment