Heap Queue in Python

A priority queue is represented by a heap data structure. It is available in Python through the “heapq” module.

In Python, the property of this data structure is that the smallest of the heap elements is popped each time (min heap). The heap structure is preserved while components are moved or popped.

Every time, the heap[0] element returns the smallest element.

Let's look at some important heap operations :

- heapify(iterable) :- The iterable is converted into a heap data structure using this feature. i.e. in heap order.

- heappush(heap, ele) :- This function inserts the element specified in the arguments into the heap. The order is changed to keep the heap structure intact.

- heappop(heap) :- This function is used to delete the smallest element from the heap and return it. The order is changed to keep the heap structure intact.

# Python code to demonstrate working of
# heapify(), heappush() and heappop()

# importing "heapq" to implement heap queue
import heapq

# initializing list
li = [5, 7, 9, 1, 3]

# using heapify to convert list into heap
heapq.heapify(li)

# printing created heap
print ("The created heap is : ",end="")
print (list(li))

# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li,4)

# printing modified heap
print ("The modified heap after push is : ",end="")
print (list(li))

# using heappop() to pop smallest element
print ("The popped and smallest element is : ",end="")
print (heapq.heappop(li))

Output :

The created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1