How to merge two sorted arrays using heapq in Python?

In this section, we will see how to use the heapq module in Python to merge two sorted lists. For example, if list1 = [10，20，30，40] and list2 = [100，200,300,400,5If '00' is returned, then after merging it will return a list3 = [10，20，30，40，100， 200、300、400、500]

To perform this task, we will use the heapq module. This module is included with Python as a standard library module. Therefore, we need to import it before using it.

import heapq

The heapq module has some attributes. These are as follows-

Method heapq.heapify(iterable)

It is used to convert an iterable dataset into a heap data structure.

Method heapq.heappush(heap, element)

This method is used to insert an element into the heap. After that, the entire heap structure is re-heapified.

Method heapq.heappop(heap)

This method is used to return and delete an element from the top of the heap, and heapify the remaining elements.

Method heapq.heappushpop(heap, element)

This method is used to insert and pop elements in a single statement.

Method heapq.heapreplace(heap, element)

This method is used to insert and pop elements in a single statement. It removes an element from the root of the heap and then inserts the element back into the heap.

Method heapq.nlargest(n, iterable, key=None)

This method is used to return n largest elements from the heap.

Method heapq.nsmallest(n, iterable, key=None)

This method is used to return n smallest elements from the heap.

Example code

import heapq
first_list = [45,　12,　63,　95,　74,　21,　20,　15,　36]
second_list = [42,　13,　69,　54,　15]
first_list = sorted(first_list)
second_list = sorted(second_list)
print('First sorted list: ')　+　str(first_list())
print('Second sorted list: ')　+　str(second_list())
final_list = list(heapq.merge(first_list, second_list))
print('The final list: ')　+　str(final_list())

Output result

First sorted list: [12,　15,　20,　21,　36,　45,　63,　74,　95]
Second sorted list: [13,　15,　42,　54,　69]
The final list: [12,　13,　15,　15,　20,　21,　36,　42,　45,　54,　63,　69,　74,　95]