Priority Queue in Python
Last Updated :
29 Aug, 2022
Priority Queues are abstract data structures where each data/value in the queue has a certain priority. For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest.
Priority Queue is an extension of the queue with the following properties.
- An element with high priority is dequeued before an element with low priority.
- If two elements have the same priority, they are served according to their order in the queue.
Various applications of the Priority queue in Computer Science are:
Job Scheduling algorithms, CPU and Disk Scheduling, managing resources that are shared among different processes, etc.
Key differences between Priority Queue and Queue:
- In Queue, the oldest element is dequeued first. While, in Priority Queue, an element based on the highest priority is dequeued.
- When elements are popped out of a priority queue the result obtained is either sorted in Increasing order or in Decreasing Order. While, when elements are popped from a simple queue, a FIFO order of data is obtained in the result.
Below is a simple implementation of the priority queue.
Python
class PriorityQueue(object):
def __init__(self):
self.queue = []
def __str__(self):
return ' '.join([str(i) for i in self.queue])
def isEmpty(self):
return len(self.queue) == 0
def insert(self, data):
self.queue.append(data)
def delete(self):
try:
max_val = 0
for i in range(len(self.queue)):
if self.queue[i] > self.queue[max_val]:
max_val = i
item = self.queue[max_val]
del self.queue[max_val]
return item
except IndexError:
print()
exit()
if __name__ == '__main__':
myQueue = PriorityQueue()
myQueue.insert(12)
myQueue.insert(1)
myQueue.insert(14)
myQueue.insert(7)
print(myQueue)
while not myQueue.isEmpty():
print(myQueue.delete())
|
Output:
12 1 14 7
14
12
7
1
Note that the time complexity of delete is O(n) in the above code. A better implementation is to use Binary Heap which is typically used to implement a priority queue. Note that Python provides heapq in the library also.
Time complexity: By using heap data structure to implement Priority Queues
Insert Operation: O(log(n))
Delete Operation: O(log(n))
Please Login to comment...