In this article, we are going to see the difference between heapq and PriorityQueue in Python.
Differences between PriorityQueue and heapq
- Python queue PriorityQueue is thread-safe, but heapq doesn’t guarantee thread safety.
- PriorityQueue implements locking to ensure thread safety, thus it is slower than heapq.
- heapq heapifies the original list inplace, while using PriorityQueue it doesn’t modify the original data.
- heapq works on the principle of binary heap, while PriorityQueue works on the basis of queue data structure and can be assigned a priority.
- It is safe to use the same PriorityQueue across multiple threads and do modifications, but in case of heapq it can lead to Data Race condition, since there are no locks while manipulating the queue.
Syntax of Using heapq and PriorityQueue
Example 1: Using heapq
Here, we have used heapify() method to convert a list of items into heap. And then we used heapop() method to pop items one by one from the heapified list.
Python3
import heapqjobs = [(1, 'eat'), (3, 'code'), (2, 'sleep')]heapq.heapify(jobs)for _ in range(len(jobs)): popped_item = heapq.heappop(jobs) print(popped_item) |
Output:
(1, 'eat') (2, 'sleep') (3, 'code')
Example 2: Using PriorityQueue
Here, we have used .put() method to push an element to the PriorityQueue and get_nowait() to pop an element from the PriorityQueue. And the loop to pop the items from the PriorityQueue breaks when the PriorityQueue raises an Empty exception, which signifies, there are no more elements to be popped.
Python3
from queue import PriorityQueue, Emptyprior_queue = PriorityQueue()jobs = [(1, 'eat'), (3, 'code'), (2, 'sleep')]for job in jobs: prior_queue.put(job) while 1: try: popped_item = prior_queue.get_nowait() print(popped_item) except Empty: break |
Output:
(1, 'eat') (3, 'code') (2, 'sleep')
Time Comparison of heapq vs PriorityQueue
Here, we have defined 2 functions for two different purpose. p_queue() function for using PriorityQueue on 10^5 data items. And heap_queue() on same size of data input list for performing operations using heapq Python module. And the main() function for time profiling on each of the mentioned 2 functions.
Python3
import timefrom queue import PriorityQueue, Emptyimport heapqdef p_queue(): prior_queue = PriorityQueue() jobs = [(x, f"This is item: {x}") for x in range(1, 10 ** 5 + 1)] for job in jobs: prior_queue.put(job) while 1: try: popped_item = prior_queue.get_nowait() except Empty: breakdef heap_queue(): jobs = [(x, f"This is item: {x}") \ for x in range(1, 10 ** 5 + 1)] heapq.heapify(jobs) for _ in range(len(jobs)): popped_item = heapq.heappop(jobs)def main(): start_time = time.perf_counter_ns() heap_queue() end_time = time.perf_counter_ns() print(f"Adding and popping item using heapq \ took: {(end_time - start_time) // 10 ** 6:.02f}ms") start_time = time.perf_counter_ns() p_queue() end_time = time.perf_counter_ns() print(f"Adding and popping item using PriorityQueue\ took: {(end_time - start_time) // 10 ** 6:.02f}ms")if __name__ == '__main__': main() |
Output:
Adding and popping item using heapq took: 154.00ms
Adding and popping item using PriorityQueue took: 375.00ms
Conclusion: It is clear from the time profiling that, heapq runs faster than PriorityQueue function. And this is obvious because PriorityQueue uses the threading module to implement a mutex structure for thread safety while manipulating items in the queue.
