What is the heapq.heapreplace() method in Python?

Overview

The heapq module is an inbuilt module in Python that offers APIs for different operations of the heap data structure. The module provides min 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 more.

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

The heapreplace method

The heapreplace method pops and returns the smallest element from the heap then pushes the given element into the heap. This method is equivalent to heappop() followed by heappush().

Syntax

heapq.heapreplace(heap, item)
  • heap: This refers to the heap to which the item has to be inserted.
  • item: This refers to the element to be inserted.

Code

import heapq
lst = [28, 2, 32, 22, 10, 1]
print("Original list - ", lst)
heapq.heapify(lst)
print("Heapified list - ", lst)
print("Calling heapreplace() ----")
pop_item = heapq.heapreplace(lst, 0)
print("The popped item - ", pop_item)
print("List after heapreplace call - ", lst)

Explanation

  • Line 1: We import the heapq module.
  • Line 3: We define a list of integers called lst.
  • Line 7: We convert the lst to a heap using the heapify method.
  • Line 9: We print the heapified list.
  • Line 11: We invoke the heapreplace() method where we add 0 to lst and store the popped element in pop_item.

In the output, we can see that the smallest value, initially 1, is popped, and then the new item 0 is pushed. The 0th index is the new heap value, i.e., 0.

Here, we can see the difference in the order of push and pop operations.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)