Python heapq example – My Programming School


86 / 100

python heapq example – My Programming School

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 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, that 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 List

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 in 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 concerning 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 one 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 Min Heap Representation

Python Heapq Module

Heapq is a Python module which gives an implementation of the Min heap. It makes use of 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 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 to a heap.

Let’s now try what capabilities does this module present.

Python Heapq Functions

The python heapq module has the next strategies:

1. heappush()

It provides a component to the heap. Don’t apply it on 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 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 outcomes 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() operate. And it pushed that at 0th place by shifting the earlier worth to 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 poped off the bottom ingredient from the heap.

3. heappushpop()

This operate 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 operate 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() operate 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 operate 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 a operate of 1 argument.

The chosen gadgets should fulfill the okay operate. 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 operate, 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 a operate of 1 argument.

The chosen gadgets should fulfill the okay operate. 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

First Exercise

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)

Second Exercise

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 (with out 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


Python Heapq and Heapq Function with Examples

Let’s now look at this topic in ingredient by answering a couple of of your regular questions first.

What is a Priority Queue?

Priority Queue is an advanced info variety (ADT) which is a more refined mannequin of a Queue. It dequeues larger-precedence devices sooner than the decrease-precedence devices. Most programming languages such as Python use Binary heap to implement it.

Python heapq, as mentioned in the beginning, gives a min-heap implementation.

What is a Heap?

A heap has quite a lot of which means in laptop computer science. Sometimes, it refers to a memory house in a program used for dynamic allocation. However, in this tutorial, we’re talking in regards to the Heap Data Structure, which is a whole binary tree. It helps in implementing priority queues (PQ), the heapsort, and some graph-based mostly algorithms.

A heap has the subsequent two variants:

  • A max-heap, in which the mom or father is more than or equal to every of its toddler nodes.
  • A min-heap, in which the mom or father is smaller or equal to the child nodes.

Below is a regular illustration of a binary heap.

Python Heapq Min Heap Representation

Python Heapq Module

Heapq is a Python module which gives an implementation of the Min heap. It makes use of Binary heap and exposes quite a lot of options to implement a priority queue.

You would possibly finally resolve many programming points using its options. For occasion, find the two largest numbers from a list of integers in Python.

There happen to be some methods to deal with this downside. However, none is as intuitive and faster than a Heapq reply.

Out of many Python heapq options, one is nlargest(). It returns a list variety object containing the required number of largest elements. Below is a short occasion sooner than we dig into the more tough ones.

Python heapq occasion

# A short heapq occasion
# Find the two largest integers from a list 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 bear in mind which you possibly can create a heap in each of these two strategies:

  • Initialize the itemizing with [].
  • Pass a pre-crammed itemizing into heapify() to rework to a heap.

Let’s now try what options does this module current.

Python Heapq Functions

The python heapq module has the subsequent methods:

1. heappush()

It gives a part to the heap. Don’t apply it on any outdated itemizing, as a substitute use the one that you just constructed using Heap options. That is how one can assure the climate are in the required order.

# heappush() Syntax
import heapq as hq
hq.heappush(heap, side)

Check out below heapq heappush() occasion.

# A short heapq.heappush() occasion

import heapq as hq
import random as r

init_list = itemizing(differ(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 itemizing
heap = []
print("Step-3: Creating heap...")

# Demonstrating heapq.heappush() function

# Printing heap content material materials to see if the smallest merchandise is at 0th index print(” a. Heap contains: “, heap) # Adding one different smaller merchandise to the heap hq.heappush(heap, 1) print(” b. Heap contains: “, heap)

This code outcomes in the subsequent:

Step-1: Seed info for the heap:  [10, 20, 30, 40, 50, 60, 70, 80, 90]
Step-2: Randomize the seed info:  [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 lower price using the heappush() function. And it pushed that at 0th place by shifting the earlier price to 1st index.

2. heappop()

It is used to take away the smallest merchandise that stays at index 0. Moreover, it moreover ensures that the next lowest replaces this place:

# heappop() Syntax
import heapq as hq
hq.heappop(heap)

Check out heapq heappop() occasion. You should append this code to the earlier heappush() occasion.

# Exercising heapq.heappop() function
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 subsequent consequence:

Step-4: Removing devices from heap...
 a. heappop() eradicated 1 from heap[10, 20, 40, 50, 30, 70, 80, 90, 60]
 b. heappop() eradicated 10 from heap[20, 30, 40, 50, 60, 70, 80, 90]
 c. heappop() eradicated 20 from heap[30, 50, 40, 90, 60, 70, 80]

It is clear from the output that heappop() at all occasions poped off the underside side from the heap.

3. heappushpop()

This function first gives the given merchandise in a Heap, then removes the smallest one and returns it. So, it is an increment of every heappush() and heappop(). But it tends to be barely faster than the two combined.

# heappushpop() Syntax
import heapq as hq
hq.heappushpop(heap, side)

Check out heapq heappushpop() occasion. You should append it to the earlier code sample.

# Exercising heapq.heappushpop() function
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 devices from heap...
 a. heappushpop() added 99 and eradicated 30 from heap[40, 60, 50, 70, 90, 99, 80]
 b. heappushpop() added 999 and eradicated 40 from heap[50, 60, 80, 70, 90, 99, 999]

4. heapify()

This function accepts an arbitrary itemizing and converts it to a heap.

# heapify() Syntax
import heapq as hq
hq.heapify(heap)

Summary – Python Heapq

With the python heapq module, you presumably can implement quite a lot of kinds of priority queues and schedulers. It has enormous utilization in completely completely different areas such as Artificial Intelligence (AI), Machine Learning, Operating strategies (OS), and in graphs.

Anyways, after wrapping up this tutorial, it’s essential to actually really feel comfortable in using Python Heapq. However, you might comply with more with examples to realize confidence.

Also, to examine Python from scratch to depth, do be taught our step-by-step Python tutorial.

python heapq example – My Programming School

For more go to Wikipedia

Have any Question or Comment?

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories

You have successfully subscribed to myprogrammingschool

There was an error while trying to send your request. Please try again.

My Programming School will use the information you provide on this form to be in touch with you and to provide updates and marketing.