Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
communitycreator

What is heapq.merge() in Python?

abhilash

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

The heapq module

The heapq module is an inbuilt module in Python that offers APIs for different operations of the heap data structure. The module provides minimum heap implementation where the key of the parent is less than or equal to those of its children. Some of the functions offered by the module are heapify, heappushpop, and so on.

Note: Refer What is a Heap? and What is the Python priority queue? to understand more about heaps and priority queues.

The merge method

The merge method merges multiple sorted iterables into a single sorted iterable. The method returns an iterator over the sorted result. This method assumes each of the iterables are sorted in ascending order.

Syntax

heapq.merge(*iterables, key=None, reverse=False)
  • iterables refers to the iterables to merge.
  • key refers to the key function that is used to extract a comparison key from each input element.
  • reverse is a boolean value. The input elements will be merged with a reverse comparison if this parameter is set to True.

Code example

Let’s look at the code below:

import heapq
def merge(iterables):
print("heapq.merge(%s) = %s" % (iterables, list(heapq.merge(*iterables))))
def merge_key(iterables, lambda_func):
print("heapq.merge(%s) = %s" % (iterables, list(heapq.merge(*iterables, key=lambda_func))))
lst1 = ['a', 'b', 'd', 'e']
lst2 = ['c', 'p', 'q', 'r']
merge([lst1, lst2])
lst1 = [('a', 1), ('b', 2), ('c', 3)]
lst2 = [('p', 15), ('q', 20), ('r', 30)]
merge_key([lst1, lst2], lambda x:x[1])

Code explanation

  • Line 1: We import the heapq module.
  • Lines 3 and 4: We define the merge function. It takes the list of iterables as input and prints the sorted merged list of elements in the iterables.
  • Lines 6 and 7: We define the merge_key function. It takes the list of iterables and key function as input and prints the sorted merged list of elements in the iterables according to the given key function.
  • Lines 9 and 10: We define two sorted lists, lst1 and lst2, containing characters.
  • Line 11: We invoke the merge function with lst1 and lst2. The output is the flattened list of elements from lst1 and lst2 in sorted order.
  • Lines 13 and 14: We re-define the two sorted lists of tuples lst1 and lst2.
  • Line 15: We invoke the merge_key function with lst1 and lst2 and the key function as a lambda expression that returns the second element of the tuple.

Output

The output is the flattened list of elements from lst1 and lst2 in sorted order as per the second element of the individual tuples.

RELATED TAGS

python
communitycreator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring