This tutorial intends to coach you on utilizing Python Heapq. It is a module in Python which makes use of the binary heap knowledge construction and implements Heap Queue a.okay.a. Priority Queue algorithm.
Interestingly, the python heapq module makes use of an everyday Python record to create Heap. It helps the addition and elimination of the smallest ingredient in O(log n) time. Hence, it is an apparent selection for implementing precedence queues.
The python heapq module contains seven capabilities, the primary 4 of which are used for heap operations. However, you must present a listing as the heap object itself.
Heap knowledge construction has a property that it at all times pops out the smallest of its ingredient (Min Heap). Also, it retains the heap construction intact regardless of any push or pop operation. The heap[0] would additionally level to the smallest worth of the Heap.
Python Heapq and Heapq Function with Examples
Let’s now look at this matter in element by answering a few of your common questions first.
Python heapq, as acknowledged at the start, gives a min-heap implementation.
What is a Heap?
A heap has a number of that means in laptop science. Sometimes, it refers to a reminiscence space in a program used for dynamic allocation. However, in this tutorial, we’re speaking about the Heap Data Structure, which is an entire binary tree. It helps in implementing precedence queues (PQ), the heapsort, and some graph-based mostly algorithms.
A heap has the next two variants:
- A max-heap, in which the mum or dad is more than or equal to each of its little nodes.
- A min-heap, in which the mum or dad is smaller or equal to the kid nodes.
Below is a common illustration of a binary heap.
Python Heapq Module
Heapq is a Python module that gives an implementation of the Min heap. It makes use of a Binary heap and exposes a number of capabilities to implement a precedence queue.
You could ultimately resolve many programming issues utilizing its capabilities. For example, find the 2 largest numbers from a listing of integers in Python.
There occur to be some ways to handle this downside. However, none is as intuitive and quicker than a Heapq answer.
Out of many Python heapq capabilities, one is nlargest(). It returns a listing sort object containing the specified variety of the largest components. Below is a short example earlier than we dig into the more sophisticated ones.
Python heapq example
# A quick heapq example
# Find the 2 largest integers from a listing of numbers
import heapq as hq
list_of_integers = [21, 67, 33, 13, 40, 89, 71, 19]
# Find two largest values
largest_nums = hq.nlargest(2, list_of_integers)
print("Two largest numbers are: ", largest_nums)The output is:
Two largest numbers are: [89, 71]
Please notice that you would be able to create a heap in both of those two methods:
- Initialize the record with [].
- Pass a pre-crammed record into heapify() to transform into a heap.
Let’s now try what capabilities this module presents.
Python Heapq Functions
The python heapq module has the next strategies:
1. heappush()
It provides a component to the heap. Don’t apply it to any outdated record, as an alternative use the one that you simply constructed utilizing Heap capabilities. That is how one can guarantee the weather are in the specified order.
# heappush() Syntax import heapq as hq hq.heappush(heap, ingredient)
Check out the under heapq heappush() example.
# A quick heapq.heappush() example
import heapq as hq
import random as r
init_list = record(vary(10, 99, 10))
print("Step-1: Seed data for the heap: ", init_list)
r.shuffle(init_list)
print("Step-2: Randomize the seed data: ", init_list)
# Creating heap from an empty record
heap = []
print("Step-3: Creating heap...")
# Demonstrating heapq.heappush() operate
# Printing heap content material to see if the smallest merchandise is at 0th index print(” a. Heap contains: “, heap) # Adding one other smaller merchandise to the heap hq.heappush(heap, 1) print(” b. Heap contains: “, heap)
This code outcome in the next:
Step-1: Seed knowledge for the heap: [10, 20, 30, 40, 50, 60, 70, 80, 90] Step-2: Randomize the seed knowledge: [70, 20, 60, 80, 90, 30, 40, 10, 50] Step-3: Creating heap... a. Heap incorporates: [10, 20, 30, 50, 90, 60, 40, 80, 70] b. Heap incorporates: [1, 10, 30, 50, 20, 60, 40, 80, 70, 90]
You can observe that heap saved the smallest merchandise at the 0th index. We added a new decrease worth utilizing the heappush() operation. And it pushed that at 0th place by shifting the earlier worth to the 1st index.
2. heappop()
It is used to take away the smallest merchandise that stays at index 0. Moreover, it additionally ensures that the subsequent lowest replaces this place:
# heappop() Syntax import heapq as hq hq.heappop(heap)
Check out heapq heappop() example. You have to append this code to the earlier heappush() example.
# Exercising heapq.heappop() operate
print("Step-4: Removing items from heap...")
out = hq.heappop(heap)
print(" a. heappop() removed {} from heap{}".format(out, heap))
out = hq.heappop(heap)
print(" b. heappop() removed {} from heap{}".format(out, heap))
out = hq.heappop(heap)
print(" c. heappop() removed {} from heap{}".format(out, heap))It will give the next outcome:
Step-4: Removing gadgets from heap... a. heappop() eliminated 1 from heap[10, 20, 40, 50, 30, 70, 80, 90, 60] b. heappop() eliminated 10 from heap[20, 30, 40, 50, 60, 70, 80, 90] c. heappop() eliminated 20 from heap[30, 50, 40, 90, 60, 70, 80]
It is clear from the output that heappop() at all times popped off the bottom ingredient from the heap.
3. heappushpop()
This operation first provides the given merchandise in a Heap, then removes the smallest one and returns it. So, it is an increment of each heappush() and heappop(). But it tends to be somewhat quicker than the 2 mixed.
# heappushpop() Syntax import heapq as hq hq.heappushpop(heap, ingredient)
Check out heapq heappushpop() example. You have to append it to the earlier code pattern.
# Exercising heapq.heappushpop() operate
print("Step-5: Adding & removing items from heap...")
new_item = 99
out = hq.heappushpop(heap, new_item)
print(" a. heappushpop() added {} and removed {} from heap{}".format(new_item, out, heap))
new_item = 999
out = hq.heappushpop(heap, new_item)
print(" b. heappushpop() added {} and removed {} from heap{}".format(new_item, out, heap))The output is:
Step-5: Adding & eradicating gadgets from heap... a. heappushpop() added 99 and eliminated 30 from heap[40, 60, 50, 70, 90, 99, 80] b. heappushpop() added 999 and eliminated 40 from heap[50, 60, 80, 70, 90, 99, 999]
4. heapify()
This operation accepts an arbitrary record and converts it to a heap.
# heapify() Syntax import heapq as hq hq.heapify(heap)
Check out heapq heapify() example.
# A quick heapq.heapify() example
import heapq as hq
heap = [78, 34, 78, 11, 45, 13, 99]
print("Raw heap: ", heap)
hq.heapify(heap)
print("heapify(heap): ", heap)Here is the output:
Raw heap: [78, 34, 78, 11, 45, 13, 99] heapify(heap): [11, 34, 13, 78, 45, 78, 99]
You can see that the heapify() operation reworked the enter record and made it a heap.
5. heapreplace()
It deletes the smallest ingredient from the Heap and then inserts a new merchandise. This operation is more environment-friendly than calling heappop() and heappush().
# heapreplace() Syntax import heapq as hq hq.heapreplace(heap, ingredient)
Check out heapq heapreplace() example.
# A quick heapq.heapreplace() example
import heapq as hq
heap = [78, 34, 78, 11, 45, 13, 99]
hq.heapify(heap)
print("heap: ", heap)
hq.heapreplace(heap, 12)
print("heapreplace(heap, 12): ", heap)
hq.heapreplace(heap, 100)
print("heapreplace(heap, 100): ", heap)The output is:
heap: [11, 34, 13, 78, 45, 78, 99] heapreplace(heap, 12): [12, 34, 13, 78, 45, 78, 99] heapreplace(heap, 100): [13, 34, 78, 78, 45, 100, 99]
6. nlargest()
It finds the n largest components from a given iterable. It additionally accepts a key which is an operation of 1 argument.
The chosen gadgets should fulfill the okay operation. If any of them fails, then the subsequent larger quantity is thought-about.
# nlargest() Syntax import heapq as hq hq.nlargest(n, iterable, key=None)
Check out heapq nlargest() example. It is requesting for two largest numbers.
# heapq.nlargest() example with out a key
import heapq as hq
heap = [78, 34, 78, 11, 45, 13, 99]
hq.heapify(heap)
print("heap: ", heap)
out = hq.nlargest(2, heap)
print("nlargest(heap, 2): ", out)The outcome is:
heap: [11, 34, 13, 78, 45, 78, 99] nlargest(heap, 2): [99, 78]
Check out one other heapq nlargest() example. It is not solely requesting for two largest numbers but additionally has an is_even() operate as the KEY.
If any of the chosen numbers fail to clear the KEY operation, then the subsequent one comes in.
# heapq.nlargest() example with key
import heapq as hq
def is_even(num):
if numpercent2 == 0: return 1
return 0
heap = [78, 34, 78, 11, 45, 13, 99]
hq.heapify(heap)
print("heap: ", heap)
out = hq.nlargest(2, heap, is_even)
print("nlargest(heap, 2): ", out)The output is:
heap: [11, 34, 13, 78, 45, 78, 99] nlargest(heap, 2): [34, 78]
7. nsmallest()
It is additionally much like the nlargest() in operation. However, it will get the n smallest components from a given iterable. It too accepts a key which is an operation of 1 argument.
The chosen gadgets should fulfill the okay operation. If any of them fails, then the subsequent smaller quantity is thought-about.
# nsmallest() Syntax import heapq as hq hq.nsmallest(n, iterable, key=None)
Check out heapq nsmallest() example. It is requesting for two smallest numbers.
# heapq.nsmallest() example
import heapq as hq
heap = [78, 34, 78, 11, 45, 13, 99]
hq.heapify(heap)
print("heap: ", heap)
out = hq.nsmallest(2, heap)
print("nsmallest(heap, 2): ", out)Here is the outcome:
heap: [11, 34, 13, 78, 45, 78, 99] nsmallest(heap, 2): [11, 13]
You can obtain related conduct via different methods, however, the heap algorithm is more reminiscence-environment friendly and even quicker.
Heapq Exercises with heapq example
Write a Python program to push components and pop off the smallest one.
import heapq as hq
heap = []
hq.heappush(heap, ('H', 9))
hq.heappush(heap, ('H', 7))
hq.heappush(heap, ('H', 4))
hq.heappush(heap, ('H', 1))
print("Elements in the heap:")
for ele in heap:
print(ele)
print("----------------------")
print("Calling heappushpop() to push element on the heap and return the smallest one.")
hq.heappushpop(heap, ('H', 11))
for ele in heap:
print(ele)The output:
Elements in the heap:
('H', 1)
('H', 4)
('H', 7)
('H', 9)
----------------------
Calling heappushpop() to push ingredient on the heap and return the smallest one.
('H', 4)
('H', 9)
('H', 7)
('H', 11)Write a Python program to carry out Heap Sort, push all gadgets to a heap, and then take off the smallest ones one after different.
import heapq as hq
def heap_sort(heap):
in_list = []
for worth in heap:
hq.heappush(in_list, worth)
return [hq.heappop(in_list) for i in range(len(in_list))]
out = heap_sort([9, 7, 5, 2, 1, 2, 8, 10, 6, 5, 4])
print(out)Here is the outcome:
[1, 2, 2, 4, 5, 5, 6, 7, 8, 9, 10]
More Exercises for Practice
There are many different issues that you could be like to unravel. Some of those are as follows:
3. Where will you find the third smallest key in a heap?
Ans. We can get the third-smallest key from:
- The nodes with a depth stage of 1 or 2
4. Where will you get the most important key in a heap?
Ans. The largest key is most definitely to be saved at an exterior/leaf node (without youngsters)
5. Describe a sequence of n insertions in a heap that takes Ω(nlogn) time to finish.
Summary – Python Heapq
With the heapq module, you possibly can implement a number of sorts of precedence queues and schedulers. It has huge utilization in completely different areas such as Artificial
Also, to examine Python from scratch to depth, do be taught our step-by-step Python tutorial.
For more depth visit Wikipedia.
