Priority Queue in Python

Priority Queue

Priority queues are abstract data structures where each element in the queue has a priority value. For example, in any airline, baggage under the “First-Class” or “Business” arrives before other baggage.

A priority Queue is a type of queue that follows the given below properties:

  • An item with higher priority will be dequeued before the item with lower priority.
  • If two elements present in the priority queue are having the same priority, then they will be served according to the order in which they are present in the queue.

The priority queue is widely used in many applications like job scheduling algorithms, CPU and Disk scheduling, and managing various resources shared between different processes, etc.

How is the Priority Value assigned in the Priority Queue?

Usually, an element’s value is considered for assigning the priority. For example, the element with bigger value will have a higher priority than the element with lower value.
We can also set priorities according to our demand.

The main difference between a queue and a priority queue:

  • In the queue, the element inserted first will be dequeued first. But in the case of a priority queue, the element which is having highest priority will be dequeued first.
  • When an element is popped out of the priority queue, the result will be in the sorted order, it can be either increasing or decreasing. While in queue elements are popped out in the order of FIFO (First in First out).

Implementation of priority queue in 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(1)
	myQueue.insert(2)
	myQueue.insert(14)
	myQueue.insert(7)
	print(myQueue)		
	while not myQueue.isEmpty():
		print(myQueue.delete())

This article tried to discuss Implementation of Priority Queue in Python. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *