Python heapq or Heap Queue Module

A heapq or Heap Queue is also known as a Priority queue. It is a special data structure that allows us to access elements from the smallest to the largest.

The smallest element is known as the minimum heap, and the largest element is known as the maximum heap.

We can implement the heap queue algorithm using the collection of functions provided by the heapq  module in Python.

Example: Creating Heap

Output:

0	
1
[9, 8, 8]
[2, 3, 4]

Importing heapq

The first step of using the heapq module in our program is importing it with the following line:

Python heapq Operations

There are several operations we can perform using a heap, which include managing data efficiently. It is useful in specific conditions such as graph algorithms, priority queues, and scheduling.

The operations that can be performed are as follows:

• Creating a Heap Queue: In the first step, a regular list is converted into a min-heap.
• Push: In this, an element is added to the heap. It is done while keeping the head property intact.
• Pop: It is used to remove and return the smallest element from the heap.
• Peek: As the name suggests, it allows us to access the smallest element, and the element does not need to be removed.
• Push and Pop: Here, the new element is pushed (added), and the smallest element is popped, which means taken out.
• Replace: Remove the smallest element and insert a new element in a single step.

Python heapq Functions

Creating a Heap Queue

In Python, a heap queue is created by converting a normal list into a min-heap by using the heapify() function. It ensures that the smallest element is always in the front in a special tree-based structure.

Syntax:

Parameter: x list to be converted into a heap.

Example: Creating Heap

Let's look at an example where we will convert a normal list into a min-heap

Output:

Heap queue: [15, 20, 25, 30, 40]

Explanation:

In the above example, we have used the heapify() function to convert a simple list into a min-heap. The first element of the heap is the smallest.

Using Heap as a Max-Heap

We can find out the largest element in the heap by completely reversing the mechanism of the heapq  module, which is a min-heap. We do this by creating a max heap using the negative values.

Example

Let's see an example where we will print the largest element from the heap.

Output:

Maximum element: 40

Explanation

In the above example, we have stored the values as negatives, which makes the largest number smallest in the heap. When accessing a value, it is multiplied by −1 to get back the original number.

Appending and Popping Elements

We can add and remove elements from the heap queue while maintaining the property of a heap.

• heapq .heappush(heap, item): This function is used to add an item to the heap.
• heapq .heappop(heap): This function is used to remove the smallest element in the heap.

Appending an Element into Heap

Let's see an example where we will add an element to the heap.

Example: Adding Element into Heap

Output:

Heap before appending an element:  [5, 15, 20, 25, 30]
Heap after adding new element:  [5, 15, 20, 25, 30, 35]

Explanation

In the above example, the original heap had 5 elements. The heapq.heappush() function is used to push or append a new element into the heap. We pushed the number 35, and the new heap was printed successfully.

Removing an Element from Heap

We can remove the element the same way we pushed an element into the heap by using the heappop() function.

Let's see an example where we will remove an element from the heap.

Example: Removing Element from Heap

Output:

Heap before popping an element: [5, 15, 20, 25, 30]
Popped element: 5
Heap after removing element: [15, 25, 20, 30]

Explanation

In the above example, we had 5 elements in the original heap named new_heap comprising 5, 15, 20, 25, 30. The heapq .heappop() function to remove or pop the smallest element in the heap, which is 5.

Appending and Popping Element Simultaneously

We can add and remove elements simultaneously from a heap using the heapq .heappushpop() function. This function enables us to push our desirable element into the heap, and the smallest element is removed at the same time.

Example: Adding and Removing Element Simultaneously

Let's see an example where we will learn how elements can be added and removed simultaneously from the heap.

Output:

Element removed: 12
Updated heap: [18, 25, 22, 40, 50]

Explanation

In the above example, we have used the heappushpop() function to first push the number 22 into the heap named numbers. Simultaneously, the smallest element present in the heap, which is 12, is removed, and the updated heap is printed.

Finding Largest and Smallest Elements

Above we have learned that heaps work on the principle of finding the min-heap, which means the smallest element.

However, we can use certain functions like nlargest() and nsmallest() to find the largest and smallest elements in the heap, respectively.

1. heapq .nlargest(n, iterable): This function returns the n largest elements from the iterable.
2. heapq .nsmallest(n, iterable): This function returns the n smallest elements from the iterable.

Output:

Highest values: [78, 56]
Lowest values: [9, 12]

Explanation

In the above example, we used the nlargest() and nsmallest() functions to extract the highest number, which was 78 and 56, and the smallest number, which was 9, and 12 from the heap named data.

Replace and Merge Operations

The heapq module in Python also offers extra heap operations such as replacing elements and merging multiple heaps.

1. Replace Operation

The Replace operation allows us to remove the present smallest element in the heap with a new element by using the heapq .heapreplace() function.

It follows a few rules, such as:

• It returns the smallest element before replacing it.
• It is faster and more efficient than using heappop() and then heappush() separately because both actions can be performed in a single operation.

2. Merge Operation

The Merge Operation allows for the concatenation of multiple sorted iterables into a single unit of sorted heap.

This entire merge operation turns out to be quite inefficient because it does notsort the algorithm from scratch. It just maintains the heap property by merging the already sorted iterables.

Example

Let's see an example where will remove an element and merge two distinct heap into a single sorted heap.

Output:

Removed element: 12
Updated heap: [18, 25, 20, 40, 35]
Merged result: [5, 10, 15, 18, 25, 20, 40, 35, 45]

Explanation

In the above example, we used the heapq .heapreplace() function to replace the smallest element 12 with 20. After this, the updated heap was printed. Then we merged both the heaps by using heapq .merge() function. It gave us a sorted heap in the output.

Difference Between heapreplace() and heappushpop() Method

There are two key differences between heapreplace() and heappushpop() methods:

Advantages of heapq Module

• The heapq module is efficient for quickly retrieving and removing the smallest element.
• Insertion and deletion operations run in O(log n) time.
• Memory-efficient since it works directly on standard Python lists.
• Simple and lightweight module for implementing priority queues.
• Useful in algorithms like scheduling, graph processing, and simulations.

Disadvantages of heapq Module

• The heapq module does not support random access to elements other than the root.
• The structure maintains partial order, not a fully sorted list.
• The search is any specific element is quite inefficient (O(n)).
• It consists of limited built-in features for complex data operations or updates.
• Not thread-safe and requires external synchronization in multithreaded programs.

Conclusion

The Python heapq Module is a special data structure that enables us to access the smallest element to the largest. Min-heap term is denoted by the smallest element, and max-heap for the largest element. We learnt about key operations such as Creating a Heap Queue, Push, Pop, Peek, Push and Pop, Replace and Merge. At last, we covered the advantages and disadvantages between heapq Module.