A priority queue is an abstract data type that operates similar to a regular queue or stack data structure, except that each element has a certain priority associated with it. The priority of the elements in the priority queue determines the order in which elements are removed from the queue. Unlike a regular queue, where elements are removed in a first-in-first-out order, a priority queue removes elements based on priority, from highest priority to lowest priority.
Priority queues have many practical applications in computer science such as operating systems task scheduling, finding shortest paths on graphs, and discrete event simulations. In this comprehensive guide, we will examine the implementation of a priority queue data structure in Python.
Table of Contents
Open Table of Contents
Overview of a Priority Queue
A priority queue consists of components like any other abstract data type:
-
Data - The data elements contained in the priority queue. These can be integers, strings, objects, etc. Each data element has an associated priority.
-
Priority - The priority associated with each element that determines its order of removal from the queue. Priorities can be numbers, where higher numeric values are higher priority. Letter grades like ‘A’, ‘B’, ‘C’ are also commonly used priorities.
-
Enqueue Method - Adds an element to the priority queue.
-
Dequeue Method - Removes the highest priority element from the queue.
The dequeued element should always have the highest priority of all elements in the queue. Elements with equal priorities can be dequeued in any order relative to each other.
Some key characteristics of a priority queue are:
- Elements are removed based on priority order, not insertion order.
- Higher priority elements are dequeued before lower priority elements.
- Elements with equal priority can be dequeued in any order relative to each other.
Below is a simple diagram of a priority queue:
# Priority Queue
# Front (Head) Back
# +---+---+---+---+---+---+
# | P | | | | | |
# +---+---+---+---+---+---+
# | 5 | 3 | 7 | 2 | 8 | 1 |
# +---+---+---+---+---+---+
# Dequeue order: 8, 7, 5, 3, 2, 1
As we can see, elements are dequeued in priority order, highest priority first. 8 has highest priority, so is dequeued first. 7 has next highest priority, so is dequeued next, and so on.
Implementing a Priority Queue in Python
There are several ways we can implement a priority queue in Python:
- List
- Sorted List
- Heap Queue
- Binary Heap
We will look at each of these implementations next.
List Implementation
The simplest priority queue implementation in python uses the list data structure. Here is an example:
# Priority Queue with Simple List
queue = []
def enqueue(element, priority):
queue.append((element, priority))
def dequeue():
highest_priority = 0
highest_index = 0
for i in range(len(queue)):
if queue[i][1] > highest_priority:
highest_priority = queue[i][1]
highest_index = i
return queue.pop(highest_index)
To enqueue, we just append a tuple of (element, priority) to the list.
To dequeue, we loop through the list to find the element with highest priority, remove it from the list and return it.
This allows us to implement basic priority queue operations in Python very easily. However, efficiency is a drawback here. Finding the highest priority element requires looping through the entire list, giving enqueue and dequeue operations O(n) time complexity.
Let’s look at a more efficient implementation next.
Sorted List Implementation
We can improve efficiency using Python’s built-in sort() method and sorted list data structure:
# Priority Queue with Sorted List
from sortedcontainers import SortedList
queue = SortedList()
def enqueue(element, priority):
queue.add((priority, element))
def dequeue():
return queue.pop()[1]
Here we maintain the queue as a sorted list of (priority, element) tuples.
To enqueue, we just add the tuple to the sorted list, which automatically inserts it in the correct sorted order.
To dequeue, we remove the highest priority element from the end of the list in O(1) time and return it.
This improves efficiency, giving us O(log n) time for enqueue and O(1) for dequeue. Much better than our first list implementation! However, we can still do better.
Heap Queue Implementation
For optimal efficiency, we can implement the priority queue with a heap queue - a specialized container in the heapq module:
# Priority Queue with Heap Queue
import heapq
queue = []
def enqueue(element, priority):
heapq.heappush(queue, (priority, element))
def dequeue():
return heapq.heappop(queue)[1]
This implementation works identical to the sorted list, except using the heapq functions to automatically maintain the elements in a heap ordered structure.
The heapq module in Python provides efficient O(log n) time for both enqueue and dequeue operations. This is the optimal efficiency we can achieve for a priority queue in Python.
However, heapq does not support changing priorities efficiently. For a more advanced implementation allowing priority changes, a binary heap is a better choice.
Binary Heap Implementation
A binary heap is commonly used to implement priority queues. It is a specialized tree-based data structure that satisfies the binary heap property - the priority of parent nodes is always greater than or equal to the priority of child nodes.
Here is an implementation of a priority queue using a binary min heap in Python:
# Priority Queue with Binary Heap
import heapq
class PriorityQueue:
def __init__(self):
self.elements = []
def enqueue(self, element, priority):
heapq.heappush(self.elements, (priority, element))
def dequeue(self):
return heapq.heappop(self.elements)[1]
def empty(self):
return len(self.elements) == 0
queue = PriorityQueue()
To insert elements in enqueue(), we use heapq.heappush() to maintain the binary heap structure.
To extract elements in dequeue(), we use heapq.heappop() to remove and return the min element while preserving the heap structure.
This implementation allows us to achieve optimal O(log n) time complexity for both enqueue and dequeue operations.
The binary heap also allows us to efficiently change the priority of existing elements, which is not possible with the basic heapq queue.
Overall, the binary heap provides the most flexibility and efficiency in implementing a priority queue in Python.
Priority Queue Applications
Now that we have looked at various implementations for a priority queue data structure in Python, let’s discuss some real-world applications that use priority queues:
Operating System Scheduling - The OS scheduler uses a priority queue to manage processes, ordering them based on priority like user interactivity, resource needs, and time limits. Higher priority processes get access to CPU resources first.
Network Traffic Control - Network routers use priority queues to order packet delivery based on priorities like latency and bandwidth allocation requirements. Higher priority packets get forwarded first.
Graph Algorithms - Graph algorithms like Dijkstra’s use a priority queue to determine next best path. The unvisited vertex with least distance is given highest priority to be selected next.
Job Schedulers - Job queues are scheduled by systems like Hadoop using priority queues, where jobs with higher business importance are prioritized.
Discrete Event Simulations - Events are stored in a priority queue and executed in timestamp order to accurately simulate real-world events. Earlier timestamp events get priority.
Data Compression - Huffman coding uses a priority queue to determine optimal prefix-free codes to compress text data.
As we can see, priority queues have many diverse real-world applications in computer science and simulation based on their ability to order elements by priority.
Summary
To summarize, here are the key points covered in this guide on implementing a priority queue in Python:
-
A priority queue orders elements based on priority and allows efficient insertion and removal.
-
We implemented a priority queue using a simple List, Sorted List, Heap Queue, and Binary Heap.
-
The binary heap provides optimal O(log n) time complexities for enqueue and dequeue.
-
Priority queues are used in many applications like operating systems, networks, and graphs.
-
In Python, the heapq module and binary heap allow efficient priority queue implementation.
-
The binary heap supports priority changes, unlike the basic heapq queue.
-
Overall, the binary heap provides the most flexibility and efficiency for a priority queue.
By mastering priority queue implementation in Python using the techniques covered in this guide, you will have a valuable data structure in your programming toolkit enabling a wide range of algorithms and applications. The binary heap implementation provides an optimal foundation you can build on to suit the needs of different use cases you may encounter.