Data Structure Python

Heap Queue (or Heapq) in Python

Heap Queue (or Heapq) in Python

Introduction

Heap is a data structure, that is mainly used to represent a priority queue. In Python, it is available by importing the heapq module. Heapq has a property that every time the smallest heap element is popped (min-heap). Each time when an element is pushed or popped the heap structure is maintained. Also when we use heap[0], it returns the smallest element. In this article, we will see different operations on the heap in python.

Creating a simple heap

Heapify(iterable) is a function that converts an iterable list into a heaping order.

Code

# importing heapq
import heapq

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

# Using heapify
heapq.heapify(l)

# printing heap
print (list(li))

Output

[1, 3, 9, 7, 5]

write your code here: Coding Playground

Appending and Popping Items Efficiently

  • heappush(heap, ele): heappush is a function that takes an argument which the element and inserts that element into the heap. The heap order is adjusted and the heap structure is maintained.
  • heappop(heap): heappop is a function that removes the smallest element in the heap and also returns it. This heap order is again adjusted and the structure is maintained.

Code

# importing heapq
import heapq

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

# using heapify
heapq.heapify(l)

# printing heap
print(list(l))

# using heappush()
heapq.heappush(l, 4)

# printing changed heap
print(list(l))

# using heappop()
print(heapq.heappop(l))

Output

[1, 3, 9, 7, 5]
[1, 3, 4, 7, 5, 9]
1

write your code here: Coding Playground

Appending and Popping simultaneously

  • heappushpop(heap, ele):- This function combines the functionality push and pop operation inside the statement, thus increasing the efficiency. Heap order is maintained after this operation.
  • heapreplace(heap, ele):- This function also does the same functionality but is different from the above function. In this function, the element is first popped and then the element is pushed. that means the value larger than the pushed element can be returned. This function returns the element that is smallest ignoring the pushed element as opposed to heappushpop().

Code

# importing "heapq" to implement heap queue
import heapq

# initializing the list 1
l1 = [5, 1, 9, 4, 3]

# initializing the list 2
l2 = [5, 7, 9, 4, 3]

# using heapify()
heapq.heapify(l1)
heapq.heapify(l2)

# using heappushpop()
print(heapq.heappushpop(l1, 2))

# using heapreplace()
print(heapq.heapreplace(l2, 2))

Output

1
3

write your code here: Coding Playground

Find the largest and smallest elements from Heap in Python

  • nlargest(k, iterable, key = fun): This method is used when we need to return the k largest elements from the iterable specified and also satisfy the key if mentioned.
  • nsmallest(k, iterable, key = fun): This method is used when we need to return the k smallest elements from the iterable specified and also satisfy the key if mentioned.

Code

# importing heapq
import heapq

# initializing list
l = [6, 7, 9, 4, 3, 5, 8, 10, 1]

# using heapify()
heapq.heapify(l)

# using nlargest
print(heapq.nlargest(3, l))

# using nsmallest
print(heapq.nsmallest(3, l))

Output

[10, 9, 8]
[1, 3, 4]

write your code here: Coding Playground