Understanding Priority Queue, With Examples

There are many kinds of queue structures in programming, each with its own advantages and applications. 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 or circular 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 an array, 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] < highest_priority:
                highest_priority = self.queue[i][1]
                highest_priority_index = i
        return self.queue.pop(highest_priority_index)[0]

    def peek(self):
        if self.is_empty():
            return None
        highest_priority = self.queue[0][1]
        for i in range(1, len(self.queue)):
            if self.queue[i][1] < highest_priority:
                highest_priority = self.queue[i][1]
        return [item for item, priority in self.queue if priority == highest_priority][0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

queue = PriorityQueue()

queue.insert("Task 1", 3)
queue.insert("Task 2", 1)
queue.insert("Task 3", 2)

print("Queue size:", queue.size())

print("Peek:", queue.peek())

while not queue.is_empty():
    task = queue.delete()
    print("Processing:", task)

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.

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 < self.head.priority:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head

            while current.next is not None and current.next.priority <= priority:
                current = current.next

            new_node.next = current.next
            current.next = new_node

    def delete(self):
        if self.is_empty():
            return None

        item = self.head.item
        self.head = self.head.next
        return item

    def peek(self):
        if self.is_empty():
            return None

        return self.head.item

    def is_empty(self):
        return self.head is None

    def size(self):
        count = 0
        current = self.head
        while current is not None:
            count += 1
            current = current.next
        return count

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, but linked lists don’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] < self.heap[self.parent_index(index)]:
            parent_index = self.parent_index(index)
            self.swap(index, parent_index)
            index = parent_index

    def heapify_down(self, index):
        smallest = index
        left_child_index = self.left_child_index(index)
        right_child_index = self.right_child_index(index)

        if left_child_index < self.size and self.heap[left_child_index] < self.heap[smallest]:
            smallest = left_child_index

        if right_child_index < self.size and self.heap[right_child_index] < self.heap[smallest]:
            smallest = right_child_index

        if smallest != index:
            self.swap(index, smallest)
            self.heapify_down(smallest)

    def insert(self, item):
        self.heap.append(item)
        self.size += 1
        self.heapify_up(self.size - 1)

    def delete(self):
        if self.is_empty():
            return None

        root = self.heap[0]
        self.heap[0] = self.heap[self.size - 1]
        self.size -= 1
        self.heap.pop()
        self.heapify_down(0)

        return root

    def peek(self):
        if self.is_empty():
            return None

        return self.heap[0]

    def is_empty(self):
        return self.size == 0

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 the while 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 the binary search tree. 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 useful data structures for 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.

The image featured at the top of this post is ©Monstar Studio/Shutterstock.com.