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.
heapreplace
methodThe 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().
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.import heapqlst = [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)
heapq
module.lst
.lst
to a heap using the heapify
method.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.