Heaps and priority queue are essential data structure and is used in various day-to-day applications. Heaps are used in operating systems, sim card storage, compiler, and interpreter design, etc. A priority queue is used in load balancing, interrupt handling, Huffman codes for data compression, and various other verticals.
For different scenarios and problems involving obtaining the best element in a dataset, the data structure has to be effective to provide an easy-to-go solution at less complexity.
Python's standard library has a heapq module that can help in such implementation. Programmers can leverage this module and data structure to perform all the low-level heap operations along with some high-level priority-driven tasks also.
What is heapq module of Python?
Heap queue (Heapq) is a unique tree data structure in which each parent node is less than or equal to the child node within that tree. In Python, programmers can implement it using the heapq module. This data structure becomes beneficial in implementing tree-like priority queues. Such a queue has the characteristics where an item with a higher value or weight has more priority for early processing. It has operations like creating, inserting, removing, and replacing elements from the heapq. Let us now try each of the operations one by one.
Common Heapq Operations:
We can use the Heapq library of Python. There are pre-defined methods that allow the programmer to perform various operations.
- heapify(iterable): This method helps in converting the iterable object into a heap data structure. It performs the conversion in heap order.
- heappush(heap, elem): This method helps in inserting the element mentioned within its arguments of the heap. Hence, the name is heap-push.
- heappop(heap): This method helps in removing and returning the smallest value from the heap. Hence it is named heap-pop.
- heapreplace(heap, elem): This method helps in replacing the smallest element within the heap with a new value provided within the method as a parameter.
- heappushpop(): This method is equivalent to a heappush() operation followed by a heappop() operation.
Program:
import heapq
itrObj = [62, 14, 43, 68, 79, 3]
# heapify() for creating and rearranging the elements
heapq.heapify(itrObj) #heapq created using iteracble object
print("The sorted set of values are:", itrObj)
Output:
Explanation:
Here, we have to first import the heapq module. Then we have to create a list (iterable object) and use the heapq.heapify() module to create the heapq data structure in a sorted order. Then, we will use the print() function to display it.
Inserting elements in the heap:
Adding any new data element to a heap helps in inserting that specific element at the last index of the heapq. But, as we know now that we can use the heapify() method to bring any newly inserted element to a proper order if it is smaller than any of the existing value.
Program:
import heapq
itrObj = [62, 14, 43, 68, 79, 3]
# heapify() for rearranging the elements
heapq.heapify(itrObj) #heapq created using iteracble object
print("The sorted set of values are:", itrObj)
heapq.heappush(itrObj, 58)
print("New set of values after inserting a value in the heapq are:", itrObj)
Output:
Explanation:
Here, we have to first import the heapq module. Then we have to create a list (using iterable object) and use the heapq.heapify() module. We have to use the heapq.heapify() module to create the heapq data structure in a sorted order. Then we have used the heapq.heappush(itrObj, 58) and passed two parameters, the first one denotes the heapq object where new element will get inserted. The second one is the element value that will be inserted.
Removing an element from heapq:
Programmers can eliminate any element residing at the first index using the heappop() function. Any element residing at index 1 will get popped out automatically from the heapq.
Program:
import heapq
itrObj = [62,14,43,68,79,3]
# heapify() for rearranging the elements
heapq.heapify(itrObj) #heapq created using iteracble object
print("The sorted set of values are:", itrObj)
heapq.heappush(itrObj,58)
heapq.heappop(itrObj)
print("New set of values after inserting a value in the heapq are:", itrObj)
Output:
Explanation:
Here, we have to first import the heapq module. Then we have to create a list (using iterable object) and use the heapq.heapify() module. We have to use the heapq.heapify() module to create the heapq data structure in a sorted order. After pushing 58, we will use the heappop() method that will pop out one element from the first index location. Then we print the result using print() function.
Replacing elements within a Heapq:
The heapreplace() method helps in removing the smallest element of the heapq and brings in a new element at some place not defined by any order in that heapq.
Program:
import heapq
itrObj = [62, 14, 43, 68, 79, 33]
# heapify() for rearranging the elements
heapq.heapify(itrObj) #heapq created using iteracble object
print("The sorted set of values are:", itrObj)
heapq.heapreplace(itrObj, 8)
print("New set of values after inserting a value in the heapq are:", itrObj)
Output:
Explanation:
Here, we have to first import the heapq module. Then we have to create a list (using iterable object) and use the heapq.heapify() module. We have to use the heapq.heapify() module to create the heapq data structure in a sorted order. Then we use the heapreplace() method to replace an element with a new one. Here we have to pass two parameters, the first one denotes the heapq object where new element will get inserted. The second one is the element value that will replace the smallest element from the heapq.
Heap Push and Pop operation simultaneously:
Using heapq module, programmers can perform both push and pop operations simultaneously using the heapq.heappushpop(heap, elem) method.
Program:
import heapq
itrObj = [62, 14, 43, 68, 79, 33]
# heapify() for rearranging the elements
heapq.heapify(itrObj) #heapq created using iteracble object
print("The sorted set of values are:", itrObj)
heapq.heappushpop(itrObj, 38)
print("New set of values after inserting a value in the heapq are:", itrObj)
Output:
Explanation:
Here, we have to first import the heapq module. Then we have to create a list (using iterable object) and use the heapq.heapify() module. We have to use the heapq.heapify() module to create the heapq data structure in a sorted order. Then we use the heappushpop() method that will perform both push and pop operations simultaneously.
Here also, we have to pass two parameters, the first one denotes the heapq object where new element will get inserted. The second one is the element value that will replace the smallest element from the heapq.
Conclusion:
Finding the right path, calculating the priority-based process in OS, storing data values in primary memory through compilers and interpreters are where this data structure is used in a practical scenario. But these high-class operations require an immense calculation of time and space complexity before actually implementing them. Heapq is beneficial because you do not have to explicitly mention the smallest element that gets the priority in this data structure.