Heapq is an abbreviation for heap and queues. They’re notable for tackling various challenges, including finding the best element in a dataset. We can optionally sort the smallest item first or vice versa when dealing with data collections. Python’s heapq belongs to the standard library. For the formation of a heap, this function uses a conventional Python list.
Heaps are physical representations of data structures. In data structures, the queue is related to the suppositional type. In determining the interface, suppositional data structures are used. The implementation, on the other hand, is usually defined by the tangible/concrete type data structures.
Heapq in Python
The heap queue algorithm is implemented in Python by the heapq package. The latter employs the min-heap, in which the parent’s key is less than or equal to that of its children. In this article, we’ll explain how to use the heapq module in Python and show you some examples of how to use it with primitive data types and objects that contain complex data.
Furthermore, both the heap and the queue perform well together when it comes to prioritization. Two things determine the priority. The first is to give the most significant element the highest property. Secondly is allocating the highest priority property to the lowest-value items. The second and more frequent technique is used by Python heapq.
Priority queue
It’s a more polished version of a standard queue. The priority queue dequeues the main queue, which subsequently does the same to the lower priority items. The Python language implements this priority queue in the form of a min-heap.
By associating items with priorities, a priority queue extends the queue. When two elements somehow share the priority, the queue will serve them in FIFO order (first-in, first-out). Despite not being at the front line, items with higher priorities are dequeued first.
A priority queue usually supports at least three operations:
- add: adds a new item to the queue’s end.
- Pop: obtains the item with the highest priority that is first in the queue.
- is_empty: checks to see if the queue is empty
A priority queue stands as an abstract data structure. Items should be arranged by priority, for example, according to abstract data structures. They do not, however, specify how they will be implemented. Data structures that are concrete, such as a binary heap, must implement a priority queue. The heapq module in Python is a popular approach to creating a priority queue.
We would allocate priorities in ascending order to create a priority queue using a min-heap. The lowest-valued item receives the highest priority. When we add a new value, the reordering process guarantees that it is stored in a heap in the position that corresponds to its priority. We then obtain the node at the top of the heap when polling things from the queue.
Sorting a heap
The heap is a complete binary tree in programming, notably data structures. A heap is applied in two ways, one at a time, to two different data types. The parent node has more children than the child node. The parent node is smaller or equal to the child node in the min-heap.
Heapq is a Python module that employs a min-heap, as previously mentioned. For example, find the least and most significant numbers given the provided list.
Functions in Heapq
Let’s look at the functions supplied by Python’s heapq model, assuming you understand how the heap data structure works.
- heappush(heap, item)- Push the value item into the heap with heappush(heap, item).
- heappop(heap) — Pop the heap and return the smallest value.
- heappushpop(heap, item) — Return the lowest value from the heap by pushing the value item into it.
- heapify(x) — Convert the list x to a heap
- heapreplace(heap, item) — Pop the smallest value from the heap and return it, then push the value item into the heap.
Heapq with Primitive Data Types: An Example Walkthrough
We’ll make a heap using the heapify function on an essential list. Though, the modules are imported using the Python library. The latter library enables all operations to be carried out.
This function rearranges all list elements by putting the smallest one first while the others are not. This function is identical to sorting, but it only applies to the first index in the case of an array. The numbers are used to begin the list. After that, use the heapify method.
Let’s look at some examples of heapq functions in action. To begin, you must import the heapq module.
import heapq
Consider the following example list num_list .
num_list = [72, 114, 33, 97, 61] heapify(num_list)
Adding a new node with a smaller value than the most significant nodes will percolate up the tree, while the larger values will percolate down. If we add one to a min-heap, one will percolate up with two at the top.
It’s worth noting that nodes on the same level don’t have to be in precise ascending order. The heap property, for example, would be preserved if 5 and 6 are swapped. The heapq module has a complete binary tree as part of its implementation. We may use the heapq module to turn an unordered list of elements into a priority queue.
The following is the outcome of heapifying this list. It’s worth noting that heapifying takes place in real-time. The heapq library’s name is used to apply and call this method, and the list is supplied as an argument. Because the user-defined function must be declared, it seems to be a built-in function. The list is printed after each call. After running the code, go to the output console.
import heapq num_list = [72, 114, 33, 97, 61] heapq.heapify(num_list) print(num_list)
It’s worth noting that the 0th index contains the smallest value of all, 33.
Let’s add the number ten to our heap.
Push an element to a heapq
If you wish to add a new item to an already existing heap, you can use the heappush() function to do so. By default, every new element is added to the last index. However, if the newly added item is the smallest, you can use the heapify function to move it to the top. If the list isn’t sorted, use heapify first. After then, you can use the push feature.
The list and the item you want to add to the list are included in the function call’s arguments. When you run the code after finishing it, you’ll notice that the list has been heapified, and the following row displays the list with the additional number at the end.
heapq.heappush(num_list,10) print(num_list)
Take the item out of the heap list (pop from a heapq)
You can then remove items from the priority queue, reordering the heap so that the item with the next greatest priority is placed first. You can use the push function to get rid of the data piece from the heapq. The zeroth index element, [0], will be removed. The heap list’s smallest element is this. Consider the following list of items. Apply the heap function to it, then eliminate the element until only the smallest element remains.
After using this function, the entire list is displayed when you use the print function. The first piece is the only one that is eliminated. The next lowest element is inserted at zero indexes in its place.
It is time to test popping an element from our heapq as follows.
print(heapq.heappop(num_list)) print(num_list) print(heapq.heappop(num_list)) print(num_list)
When we pop from our heap, the smallest value from the heap is removed and returned. The number 10 is no longer in our stack.
Replace one of the heap’s elements (heapreplace() )
Aside from pop and push, the heapq module also provides the heapreplace function, which pops an object and immediately pushes a new one onto the heap. Let’s think about how to replace an item in a heap. Like with previous functions, the initial step is to heapify the list. The heapified list and the element to be entered instead of another item are passed to the replacement function.
Keep in mind that the smallest number is permanently deleted, and the new number is assigned to an undefined location, or the order is unknown. Let’s have a look at the heapreplace() function now. Allow us to heapreplace the value 33 in a heap.
print(heapq.heapreplace(num_list,32)) print(num_list)
another heapreplace() example
num_list= [7, 5, 3, 10, 8, 4, 9] heapq.heapify(num_list) print(num_list) heapq.heapreplace(num_list, 6) print(num_list)
The order of push and pop activities in the heappushpop() and heapreplace() routines differ. As you can see, the lowest value, 32, gets popped first, followed by our new value, 3. The value of the 0th index in the new heap is 3.
heappushpop()
The list is now subjected to two combined processes. The first is heappushpop(), and the second is heapreplace(), which is already well-known, as we have covered above. We’ll take two lists and heapify them independently in this example. The heappushpop() function will accept an item and add it to the list while removing the smallest item. Heappushpop reverses the heapreplace order of operations, pushing first and popping last.
Let’s have a look at the heappushpop() routines in action. Let’s take the value 32 and heappushpop it.
print(heapq.heappushpop(num_list,32)) print(num_list)
Example: heappushpop() and heapreplace()
import heapq # list one list_one =[10,12,14,11,8] # list two list_two =[10,12,14,11,7] # heapify() is responsible for converting a list into a heap heapq.heapify(list_one) heapq.heapify(list_two) # heappushpop() is responsible for pushing and popping items simultaneously print(heapq.heappushpop(list_one,9)) # using heapreplace() to both push and pop items at the same time print(heapq.heapreplace(list_two, 8))
The first print statement ejected a number, while the second replaced a new number with the smaller one.
Example: heappushpop()
num_list= [7, 5, 3, 10, 8, 4, 9] heapq.heapify(num_list) print(num_list) heapq.heappushpop(num_list, 4) print(num_list)
When you need to conduct a push and pop in quick succession, or vice versa, the last two approaches, heappushpop() and heapreplace(), are usually very efficient. The comparison procedures are the subsequent operations to be used.
Nsmallest
Nsmallest returns the smallest element in the list out of all the others. The list is heapified first, and then both operations are applied line by line.
import heapq # list initialization new_list =[6,7,9,4,3,5,8,10, 1] heapq.nsmallest(2,new_list)
An argument accompanies the list. The two smallest numbers are to be chosen according to this logic.
Nlargest
Nlargest returns the most significant item and fulfills the condition by using the key if one is provided. Below is a simple implementation to illustrate this.
import heapq # list initialization new_list =[6,7,9,4,3,5,8,10, 1] heapq.nlargest(2,new_list)
How to Use Objects in Heapq?
In the previous example, we showed how to use heapq functions with simple data types like integers. Similarly, we may organize complex data like tuples or strings using objects and heapq methods. For this, we’ll need a wrapper class that fits our circumstances. Consider the following scenario: you wish to store strings and sort them from shortest to most considerable in length. The following is a diagram of our wrapper class.
class DataWrap:
def __init__(self, data):
self.data = data
def __lt__(self, other):
return len(self.data) < len(other.data)
The logic to compare the lengths of strings is contained in the lt function (it is the operator overloading function for comparison operators; >, ==, >= and <=). Next, we test creating a heap of strings.
# Create list of strings
my_languages = ["Python", "Django", "C", "Rails", "Angular"]
# Initialising
sorted_strings = []
# Wrap strings and push to heap
for s in my_languages:
heapObj = DataWrap(s)
heapq.heappush(sorted_strings, heapObj)
# Print the heap
for myObj in sorted_strings:
print(myObj.data, end="\t")
The following is the result of printing things from the heap. It’s worth noting that the shortest word, go, is at the top of the list. Wrapping strings allows you to try out various heapq routines.
Using Heapq to implement a Max Heap
Using heapq, we can implement a maximum heap. To order the greatest value to the front, alter the comparison operator in the lt function. Let’s attempt the same thing with strings and their lengths, as in the last example.
class DataWrap:
def __init__(self, data):
self.data = data
def __lt__(self, other):
return len(self.data) > len(other.data)
# Create list of strings
my_languages = ["Python", "Django", "C", "Rails", "Angular"]
# Initialising
sorted_strings = []
# Wrap strings and push to heap
for s in my_languages:
heapObj = DataWrap(s)
heapq.heappush(sorted_strings, heapObj)
# Print the heap
for myObj in sorted_strings:
print(myObj.data, end="\t")
Notice how the length comparison has altered in the DataWrap class’s lt function. The following is the result of printing things from this heap. It’s worth noting that the longest word is written is now at the top of the stack.
Heapq-based Custom Priority Queue
In the previous example, we utilized the heap modules to convert a list into a priority queue. We used the heap module’s operations to alter the list explicitly. Because we may still interact with the list through the list interface, this is prone to errors and can mess up our priority queue. Assume we establish a priority queue, and when someone uses the list’s ordinary append function to append a member.
num_list= [7, 5, 3, 10, 8, 4, 9] heapq.heapify(num_list) print(num_list) num_list.append(2) print(num_list)
The number two is now near the back of the line rather than at the front. We can wrap the list in a new wrapper class that uses the heap to get around this issue.
class PriorityQueue:
def __init__(self, new_elements = None):
if(new_elements == None):
self.new_elements = list()
elif type(new_elements) == list:
heapq.heapify(new_elements)
self.new_elements = new_elements
def __str__(self):
return str(self.new_elements)
# function is responsible for ascertaining if the queue is empty
def isEmpty(self):
return len(self.new_elements) == 0
# code snippet to insert an element in the queue
def push(self, new_elements):
heapq.heappush(self.new_elements, new_elements)
# code to pop an element based on Priority
def pop(self):
heapq.heappop(self.new_elements)
The constructor of the priority queue class accepts an optional list of beginning values as a parameter. In the presence of an initial values list, we heapify it to build the priority queue’s order and then assign it to the element instance variable.
#creating an empty priority queue pq = PriorityQueue() #creating a priority queue with initial values pq = PriorityQueue([7, 5, 3, 10, 8, 4, 9]) print(pq)
We can now perform push and pop operations. The lowest value (with the highest priority) is always at the front line.
from queue import PriorityQueue pq = PriorityQueue() pq.put(5) pq.put(4) pq.put(1) pq.put(2) pq.put(5) print(pq.get()) print(pq.get()) print(pq.get()) print(pq.get()) print(pq.get())
Conclusion
We are hopeful that this article has been helpful and informative to help you ace through the heapq module. Please feel free to experiment with the provided code. It is an article that enumerates all of the primary heap and queue functions and operations to work as a module.
This python feature allows the user to sort the first element in a sorted array; therefore, if you want to know the first element in a sorted array, use the heapq function. Other elements, on the other hand, are not ordered. Heap is also utilized in operating systems and artificial intelligence. After reading this guide, you’ll be well-versed with heapq and its python routines.
