Heap queue (or heapq) in Python

Last Updated : 22 Mar, 2023

Heap data structure is mainly used to represent a priority queue. In Python, it is available using the “heapq” module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time. Let’s see various Operations on the heap in Python.

Creating a simple heap

The heapify(iterable):- This function is used to convert the iterable into a heap data structure. i.e. in heap order.

Python3

# importing "heapq" to implement heap queue
import heapq
 
# initializing list
li = [5, 7, 9, 1, 3]
 
# using heapify to convert list into heap
heapq.heapify(li)
 
# printing created heap
print ("The created heap is : ",(list(li)))

Output

The created heap is :  [1, 3, 9, 7, 5]

Appending and Popping Items Efficiently

heappush(heap, ele): This function is used to insert the element mentioned in its arguments into a heap. The order is adjusted, so that heap structure is maintained.
heappop(heap): This function is used to remove and return the smallest element from the heap. The order is adjusted, so that heap structure is maintained.

Python3

# importing "heapq" to implement heap queue
import heapq
 
# initializing list
li = [5, 7, 9, 1, 3]
 
# using heapify to convert list into heap
heapq.heapify(li)
 
# printing created heap
print("The created heap is : ", end="")
print(list(li))
 
# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li, 4)
 
# printing modified heap
print("The modified heap after push is : ", end="")
print(list(li))
 
# using heappop() to pop smallest element
print("The popped and smallest element is : ", end="")
print(heapq.heappop(li))

Output

The created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1

Appending and Popping simultaneously

heappushpop(heap, ele):- This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
heapreplace(heap, ele):- This function also inserts and pops elements in one statement, but it is different from the above function. In this, the element is first popped, then the element is pushed. i.e, the value larger than the pushed value can be returned. heapreplace() returns the smallest value originally in the heap regardless of the pushed element as opposed to heappushpop().

Python3

# importing "heapq" to implement heap queue
import heapq
 
# initializing list 1
li1 = [5, 1, 9, 4, 3]
 
# initializing list 2
li2 = [5, 7, 9, 4, 3]
 
# using heapify() to convert list into heap
heapq.heapify(li1)
heapq.heapify(li2)
 
# using heappushpop() to push and pop items simultaneously
# pops 2
print("The popped item using heappushpop() is : ", end="")
print(heapq.heappushpop(li1, 2))
 
# using heapreplace() to push and pop items simultaneously
# pops 3
print("The popped item using heapreplace() is : ", end="")
print(heapq.heapreplace(li2, 2))

Output

The popped item using heappushpop() is : 1
The popped item using heapreplace() is : 3

Find the largest and smallest elements from Heap in Python

nlargest(k, iterable, key = fun): This function is used to return the k largest elements from the iterable specified and satisfy the key if mentioned.
nsmallest(k, iterable, key = fun): This function is used to return the k smallest elements from the iterable specified and satisfy the key if mentioned.

Python3

# Python code to demonstrate working of
# nlargest() and nsmallest()
 
# importing "heapq" to implement heap queue
import heapq
 
# initializing list
li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1]
 
# using heapify() to convert list into heap
heapq.heapify(li1)
 
# using nlargest to print 3 largest numbers
# prints 10, 9 and 8
print("The 3 largest numbers in list are : ", end="")
print(heapq.nlargest(3, li1))
 
# using nsmallest to print 3 smallest numbers
# prints 1, 3 and 4
print("The 3 smallest numbers in list are : ", end="")
print(heapq.nsmallest(3, li1))

Output

The 3 largest numbers in list are : [10, 9, 8]
The 3 smallest numbers in list are : [1, 3, 4]

Example:

Python3

import heapq
 
# Initialize a list with some values
values = [5, 1, 3, 7, 4, 2]
 
# Convert the list into a heap
heapq.heapify(values)
 
# Print the heap
print("Heap:", values)
 
# Add a new value to the heap
heapq.heappush(values, 6)
 
# Print the updated heap
print("Heap after push:", values)
 
# Remove and return the smallest element from the heap
smallest = heapq.heappop(values)
 
# Print the smallest element and the updated heap
print("Smallest element:", smallest)
print("Heap after pop:", values)
 
# Get the n smallest elements from the heap
n_smallest = heapq.nsmallest(3, values)
 
# Print the n smallest elements
print("Smallest 3 elements:", n_smallest)
 
# Get the n largest elements from the heap
n_largest = heapq.nlargest(2, values)
 
# Print the n largest elements
print("Largest 2 elements:", n_largest)

Output

Heap: [1, 4, 2, 7, 5, 3]
Heap after push: [1, 4, 2, 7, 5, 3, 6]
Smallest element: 1
Heap after pop: [2, 4, 3, 7, 5, 6]
Smallest 3 elements: [2, 3, 4]
Largest 2 elements: [7, 6]

This program creates a heap queue using the heapq module in Python and performs various operations such as converting a list into a heap, adding a new value to the heap, removing the smallest element from the heap, getting the n smallest and n largest elements from the heap.

Note that the heapq module in Python provides functions for performing heap operations on lists in-place, without creating a separate data structure for the heap. The heapq module is efficient and easy to use, making it a popular choice for implementing priority queues and other data structures in Python.

Advantages of using a heap queue (or heapq) in Python:

Efficient: A heap queue is a highly efficient data structure for managing priority queues and heaps in Python. It provides logarithmic time complexity for many operations, making it a popular choice for many applications.
Space-efficient: Heap queues are space-efficient, as they store elements in an array-based representation, minimizing the overhead associated with node-based data structures like linked lists.
Easy to use: Heap queues in Python are easy to use, with a simple and intuitive API that makes it easy to perform basic operations like inserting, deleting, and retrieving elements from the heap.
Flexible: Heap queues in Python can be used to implement various data structures like priority queues, heaps, and binary trees, making them a versatile tool for many applications.

Disadvantages of using a heap queue (or heapq) in Python:

Limited functionality: Heap queues are primarily designed for managing priority queues and heaps, and may not be suitable for more complex data structures and algorithms.
No random access: Heap queues do not support random access to elements, making it difficult to access elements in the middle of the heap or modify elements that are not at the top of the heap.
No sorting: Heap queues do not support sorting, so if you need to sort elements in a specific order, you will need to use a different data structure or algorithm.
Not thread-safe: Heap queues are not thread-safe, meaning that they may not be suitable for use in multi-threaded applications where data synchronization is critical.

Overall, heap queues are a highly efficient and flexible data structure for managing priority queues and heaps in Python, but may have limited functionality and may not be suitable for all applications.

GeeksforGeeks

Improve

Previous Article

hashlib module in Python

Python Time Module

Similar Reads

Heap and Priority Queue using heapq module in Python

Heaps are widely used tree-like data structures in which the parent nodes satisfy any one of the criteria given below. The value of the parent node in each level is less than or equal to its children's values - min-heap.The value of the parent node in each level higher than or equal to its children's values - max-heap. The heaps are complete binary

Merge two sorted arrays in Python using heapq

Given two sorted arrays, the task is to merge them in a sorted manner. Examples: Input : arr1 = [1, 3, 4, 5] arr2 = [2, 4, 6, 8] Output : arr3 = [1, 2, 3, 4, 4, 5, 6, 8] Input : arr1 = [5, 8, 9] arr2 = [4, 7, 8] Output : arr3 = [4, 5, 7, 8, 8, 9] This problem has existing solution please refer Merge two sorted arrays link. We will solve this proble

Python heapq to find K'th smallest element in a 2D array

Given an n x n matrix and integer k. Find the k'th smallest element in the given 2D array. Examples: Input : mat = [[10, 25, 20, 40], [15, 45, 35, 30], [24, 29, 37, 48], [32, 33, 39, 50]] k = 7 Output : 7th smallest element is 30 We will use similar approach like K’th Smallest/Largest Element in Unsorted Array to solve this problem. Create an empty

Heapq with custom predicate in Python

Prerequisite: heapq module The heapq module has several functions that take the list as a parameter and arranges it in a min-heap order. The problem with these functions is they expect either a list or a list of tuples as a parameter. They do not support comparisons between any other iterable or objects. For example, consider a dictionary that has

Difference Between heapq and PriorityQueue in Python

In this article, we are going to see the difference between heapq and PriorityQueue in Python. Differences between PriorityQueue and heapqPython queue PriorityQueue is thread-safe, but heapq doesn't guarantee thread safety.PriorityQueue implements locking to ensure thread safety, thus it is slower than heapq.heapq heapifies the original list inplac

heapq in Python to print all elements in sorted order from row and column wise sorted matrix

Given an n x n matrix, where every row and column is sorted in non-decreasing order. Print all elements of matrix in sorted order. Examples: Input : mat= [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50]] Output : Elements of matrix in sorted order [10, 15, 20, 25, 27, 29, 30, 32, 33, 35, 37, 39, 40, 45, 48, 50] This problem h

How to implement Priority Queue - using Heap or Array?

A Priority Queue is a data structure that allows you to insert elements with a priority, and retrieve the element with the highest priority. You can implement a priority queue using either an array or a heap. Both array and heap-based implementations of priority queues have their own advantages and disadvantages. Arrays are generally easier to impl

Why is Binary Heap Preferred over BST for Priority Queue?

A typical Priority Queue requires following operations to be efficient. Get Top Priority Element (Get minimum or maximum)Insert an elementRemove top priority elementDecrease Key A Binary Heap supports above operations with following time complexities: O(1)O(Logn)O(Logn)O(Logn) A Self Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc c

How to implement stack using priority queue or heap?

How to Implement stack using a priority queue(using min heap)? Asked In: Microsoft, Adobe. Solution: In the priority queue, we assign priority to the elements that are being pushed. A stack requires elements to be processed in the Last in First Out manner. The idea is to associate a count that determines when it was pushed. This count works as a k

Priority Queue using Binary Heap

Priority Queue is an extension of the queue with the following properties: Every item has a priority associated with it.An element with high priority is dequeued before an element with low priority.If two elements have the same priority, they are served according to their order in the queue.A Binary Heap is a Binary Tree with the following proper

Article Tags :

Practice Tags :