Last Updated on June 29, 2022 by Ria Pathak
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.
List of various Operations on the heap:
-
heapify(iterable): With the help of this function, the iterable object is converted into a heap data structure. i.e. in heap order.
-
heappush(heap, element): With the help of this function, an element passed as an argument in the function is inserted in the heap. And for maintaining the properties of Heap, adjustment is made in the order of the nodes.
-
heappop(head): For removing the smallest element from the heap, this function is used. The order is adjusted, for maintaining heap properties.
-
heappushpop(heap, element): This function has functionality of both insertion and popping of elements in a single statement. Properties of the heap are to be maintained after this function.
-
heapreplace(heap, element): This function also has functionality of both insertion and popping of elements in a single statement. But it is quite different from the above as in this function, the element is first popped, then the element is pushed in the heap. i.e. values larger than the pushed value can be returned. In heapreplace(), the smallest value is returned in the heap regardless of the pushed element as opposed to heappushpop().
-
nlargest(k, iterable, key = fun): This function will return the k largest element present in the iterable which satisfies the key if mentioned.
-
nsmallest(k, iterable, key = fun): This function will return the k smallest element present in the iterable which satisfies the key if mentioned.
-
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.
Code Implementation
import heapq
li = [5, 3, 6, 2, 4]
heapq.heapify(li)
print ("The created heap is : ",end="")
print (list(li))
heapq.heappush(li,1)
print ("The modified heap after pushing the key is in the heap : ",end="")
print (list(li))
print ("The smallest element which is popped from the heap is : ",end="")
print (heapq.heappop(li))
print ("The popped item using heappushpop() function is : ",end="")
print (heapq.heappushpop(li, 11))
print ("The popped item using heapreplace() function is : ",end="")
print (heapq.heapreplace(li, 1))
print("The 3 largest numbers in list are : ",end="")
print(heapq.nlargest(2, li))
print("The 3 smallest numbers in list are : ",end="")
print(heapq.nsmallest(3, li))
Output:
The created heap is : [2, 3, 6, 5, 4]
The modified heap after pushing the key is in the heap : [1, 3, 2, 5, 4, 6]
The smallest element which is popped from the heap is : 1
The popped item using heappushpop() function is : 2
The popped item using heapreplace() function is : 3
The 3 largest numbers in list are : [11, 6]
The 3 smallest numbers in list are : [1, 4, 5]
This article tried to discuss the Heap queue or heapq in Python. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps at Prepbytes