Merge two sorted arrays in Python using heapq

Last Updated on July 6, 2022 by Ria Pathak

Heap

Heap Data structure primarily focuses on representing priority queue. In Python, there is an inbuilt module “heapq” which is used for implementing Heap data structure. By default, Min Heap is implemented in the heapq, in which every time the smallest element from the heap is popped out. At the 0th index, the smallest element is stored in the heap. Every time in the process of insertion and deletion of any key, the heap property is maintained in the process.

Example: Input: arr1 = [1, 3, 5] arr2 = [2, 4, 6] Output: result = [1, 2, 3, 4, 5, 6]

The given problem will be solved using the merge() function present in the heapq module in python. The merge() function takes more than 1 array as a parameter and returns the merged array to the user.

Code Implementation

from heapq import merge

def mergeArray(arr1,arr2):
	return list(merge(arr1, arr2))

if __name__ == "__main__":
	arr1 = [1, 3, 5]
	arr2 = [2, 4, 6]
	print (mergeArray(arr1, arr2))

Output: [1, 2, 3, 4, 5, 6]

List of some Properties of heapq module:

• heapq.merge(*iterables): This function is used to combine multiple sorted iterables into a single sorted iterable. It returns an iterator over the sorted values.

• heapq.heappush(original_heap, key): This function will push the value of the key into the heap, by maintaining the properties of the heap.

• heapq.heappop(original_heap): This function will pop and return the smallest element from the heap. IndexError will be raised if the heap is empty.

• heapq.heapify(x): This function is used to build a heap from list x, in-place, in linear time.

• heapq.heappushpop(original_heap, key): This function will push the value of the key in the heap, and then pop and return the smallest element from the heap. This whole function is faster than heappush() followed by heappop() functions.

This article tried to discuss the concept of Merging two sorted arrays in Python using heapq . Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps at Prepbytes