Before we get into implementing a priority queue in Python, let us first understand what a priority queue is. Priority queues are data structures where each element in the queue has a certain priority. A priority queue sorts and dequeues elements based on their priority.
- High priority element is dequeued before low priority element.
- In the case of elements having the same priority, they are dequeued by their order.
##implement using low priority elements to high priority elements pq= pq.append(100) pq.append(90) pq.append(80) pq.append(70) pq.append(60) pq.append(50) pq.append(40) pq.append(30) pq.append(20) pq.append(10) print(pq) pq.sort() print(pq) pq.pop() pq.pop() pq.pop() pq.pop() print(pq)
A data structure is in the form of a binary tree. They are a common way of implementing a priority queue. The element at the root of the tree will always have the highest priority.
Trees are non-linear data structures that represent nodesconnected by edges. Each tree consists of a root node as the Parent node, and the left node and right node as Child nodes.
A binary tree can be represented by using a list where every node consists of three fields. The first field for storing value of root node, second for storing list that represents the left subtree, and third for storing list that represents the right subtree.
Syntax: [root node, left subtree as list, right subtree as list]
Note: A binary heap is either maximum or minimum.
1.Min-heap: The value of a parent node is less than or equal to its children nodes.
2.Max-Heap: The value of a parent node is greater than or equal to its children nodes.
Heap queue (heapq): It is an implementation of the priority queue algorithm in which the properties of the min-heap are preserved.
Note: Refer above for the definition of min-heap.
1.heapify(iterable): Conversion of the iterable into a heap data structure.
2.heappush(heap, element): To insert the element argument into the heap.
3.heappop(heap): To remove the smallest element from the heap.
4.heappushpop(heap, element): To combine the function of both push (the element) and pop (the smallest element) in one line.
5.heapreplace(heap, element): The smallest element is first popped, then the element argument is pushed.
# Refer above text for more understanding of code # importing "heapq" to implement heap queue import heapq # initializing list list1 = [1, 5, 10, 15, 20] # to convert list into heap heapq.heapify(list1) print ("Initial heap: ", list1) # to push elements into heap heapq.heappush(list1, 3) # print changed heap print ("Changed heap: ", list1) # to pop smallest element print ("The smallest element is popped:", heapq.heappop(list1)) # print the updated heap print ("Updated heap: ",list1) # to push and pop items simultaneously print ("The popped item using heappushpop() is : ",list1) print (heapq.heappushpop(list1, 3)) # to push and pop items simultaneously print ("The popped item using heapreplace() is : ",list1) print (heapq.heapreplace(list1, 2))
Heap is generally favoured for implementing priority queues as they provide better performance than arrays or linked lists. They are used to execute the program because of the maximum and minimum elements at the root of the tree.