Python heap implementation using heapq module

In this post, you will learn about the heap queue implementation in Python using the heapq module with several operations. This module uses the binary heap data structure and creates a heap using a regular Python list. Before using this module, you should recall the priority queue and head sort.

Priority Queue

This module gives us a brisk and simple approach to built any sort of priority queue for your application. The elements in the priority queue have some priority. The priority of the element is used to determine the order in which the elements will be processed. The element with the highest priority is processed first. This is a very useful data structure, basically used in all kinds of scheduling processes.

Heap Sort

In Heap Sort, we are using a Binary Search Tree for sorting. In this, all elements are inserted into a tree. Heap sort requires more space than other sorting methods. It is a stable sort and requires constant space for sorting. The heap tree can be of two types- Max Tree and Min Tree.

• Max Tree- The root node has the highest key value, then the child node elements.
• Min Tree- The root node has the lowest key value, then the child node elements.

Heap sort basically works in two phases. Suppose an array A has n elements, it sorts the array in two phases.

• First, build a heap from the elements of the array.
• In the second phase, it repeatedly deletes the root element from the heap that was built in the first phase and place the element in the last empty location of the array.

Python Heapq Module

The Heapq is a Python module which gives an implementation of the min heap. It utilizes binary search and opens several functions to implement a priority queue. This module is pre-installed with Python, so there is no need to install it separately using pip. This module may solve many programming issues, like, to find the largest numbers from a list of integers or to find the smallest numbers from the list in Python.

Import heapq module

First, we need to import this using the following command-

import heapq

Python heapq example

Here is the simple example of Python heapq module to find three largest numbers and three smallest numbers from the list.

import heapq as hq

lists = [19, 39, 78, 29, 52, 11, 23]

# Get three largest values
largest_values = hq.nlargest(3, lists)

# Get three smallest values
smallest_values = hq.nsmallest(3, lists)

print("Three largest numbers are: ", largest_values)
print("Three smallest numbers are: ", smallest_values)

Three largest numbers are:  [78, 52, 39]
Three smallest numbers are:  [11, 19, 23]

Python Heapq Function

The heapq module of the Python has some methods that implement heap operations on lists. These are the following methods-

heappush()

The heappush() method is used to push elements to the heap. The syntax is-

hq.heappush(heap, element)

Here, we have mentioned the example of the heappush() method.

import heapq as hq

heap_elems = [19, 39, 78, 29, 52, 11, 23]

print("The elements of head are: ",end="")
print (list(heap_elems))

#  push elements into heap 
hq.heappush(heap_elems, 33) 

print("The modified heap after push is : ",end="") 
print (list(heap_elems))

The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after push is : [19, 39, 78, 29, 52, 11, 23, 33]

heappop()

The Python heapq module defines heappop() method to pop the smallest element while protecting the heap property. The syntax is -

heappop(heap)

Here, we have mentioned the example of the heappop() method.

import heapq as hq

heap_elems = [19, 39, 78, 29, 52, 11, 23]

print("The elements of head are: ",end="")
print (list(heap_elems))

#  pop elements into heap 
hq.heappop(heap_elems) 

print("The modified heap after pop is : ",end="") 
print(list(heap_elems))

The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after pop is : [23, 39, 78, 29, 52, 11]

heappushpop()

The heappushpop() method is equivalent to heappush() followed by heappop(). The syntax of heappushpop() is-

heappushpop(heap)

Here is the example of heappushpop().

import heapq as hq

heap_elems = [19, 39, 78, 29, 52, 11, 23]

print("The elements of head are: ",end="")
print(list(heap_elems))

hq.heappushpop(heap_elems) 

print("The modified heap is : ",end="") 
print(list(heap_elems))

The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after push pop is : 19
[23, 39, 78, 29, 52, 11, 23]

heapify()

This function heapify() accepts an arbitrary list and converts it to a heap. The syntax of heapify() is-

import heapq as hq

heap_elems = [19, 39, 78, 29, 52, 11, 23]

print("The elements of head are: ",end="")
print(list(heap_elems))

#  convert elements into heap 
hq.heapify(heap_elems) 

print("The heap is : ",end="") 
print(list(heap_elems))

The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The heap is : [11, 29, 19, 39, 52, 78, 23]

heapreplace()

It erases the smallest element from the heap and then inserts a new item. This function is more efficient than calling heappop() and heappush(). The syntax of heapreplace() is-

heapreplace(heap, element)

Here is the example of heapreplace() -

import heapq as hq

heap_elems = [19, 39, 78, 29, 52, 11, 23]

print("The elements of head are: ",end="")
print(list(heap_elems))

hq.heapreplace(heap_elems, 20 )

print("The modified heap after heapreplace is : ",end="") 
print(heap_elems )

The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after heapreplace is : [20, 39, 78, 29, 52, 11, 23]

Related Articles

Python program to sum all the numbers in a list
Difference between tuple and list in Python
Alphabetical order Python
Write a program to read two numbers and print their quotient and remainder in python
ASCII value in Python
Greatest common divisor (GCD) in Python
Python nonlocal keyword
Prime factor Python
casefold in Python
strip function in Python
Convert array to list Python
Remove element from list Python
Convert list to dictionary Python
Python dict inside list
Convert list to string Python
Remove last element from list Python
Convert string to list Python
Python add list to list
Difference between tuple and list in Python
Alphabetical order Python