Heap queue or commonly referred to as priority queue is an algorithm that maintains elements sorted based on their priority using a data structure called the heap. Heap is a binary tree data structure where each node’s value is less than or equal to its children. This makes sure that the minimum element is present at the root of the tree. Each time we pop a value from the heap, it'll retrieve the root node value (which is smallest) and then rearrange the tree to make it heap again satisfying its property (node value smaller or equal to its children). Python provides us with the module named **heapq** which provides an implementation of heap queue hence we don't need to write one of our own.

As a part of this tutorial, we'll be demonstrating the usage of various methods of **heapq** module. We'll explain them with simple and easy to understand examples.

As a part of our first example, we'll explain how we can create a heap from a list using **heapify()** method.

**heapq.heapify()**- It takes as input a list and transforms a list into a heap in linear time (**O(n)**). It performs this operation in place without returning anything.

We are first creating a list of 20 random numbers in the range 1-20. We are then calling **heapify()** method on them to translate the list to a heap. We are printing the list before it was heap and after it was converted to the heap.

```
import heapq
import random
random.seed(123)
heap = [random.randint(1, 20) for i in range(20)]
print("Initial List : {}".format(heap))
heapq.heapify(heap)
print("Heap : {}".format(heap))
```

Below we have shown the heap that was created above. We have represented it as a binary tree to better understand it. We can confirm that all node has value less than or equal to its children.

**Heap**

```
2
6 2
8 9 2 3
11 11 9 11 11 4 6 5
13 18 14 18 18
```

Our second example is another example explaining the usage of the **heapify()** method. We are this time passing a tuple to the method. It takes the first element of the tuple to create a heap. This can be helpful in situations where we are some important number like priority present as the first element of the item.

```
import heapq
import random
random.seed(123)
heap = [(random.randint(1, 10), str(i+1)) for i in range(10)]
print("Initial List : {}".format(heap))
heapq.heapify(heap)
print("Heap : {}".format(heap))
```

Our third example also explains the usage of the **heapify()** method but it uses string elements.

```
import heapq
import random
random.seed(123)
heap = [(str(random.randint(1, 10))) for i in range(10)]
print("Initial List : {}".format(heap))
heapq.heapify(heap)
print("Heap : {}".format(heap))
```

Our fourth example again builds heap using **heapify()** method but uses alphabet characters as heap items.

```
import heapq
heap = ["C", "D", "E", "R", "A", "B", "Z", "S", "T", "F", "G"]
print("Initial List : {}".format(heap))
heapq.heapify(heap)
print("Heap : {}".format(heap))
```

**Heap**

```
A
C B
R D E Z
S T F G
```

Our fifth example explains how we can push new items on the heap using **heappush()** method.

**heappush()**- It accepts the heap and the item we want to push as input and pushes that item on the heap. It’s an in-place operation.

We are looping 10 times and adding a random float to the heap each time using **heappush()**. We are the printing heap at last as well.

```
import heapq
import random
random.seed(123)
heap = []
for i in range(10):
val = random.randint(1,10) + random.random()
heapq.heappush(heap, val)
print("Heap : ", heap)
```

As a part of our sixth example, we are demonstrating how we can pop items from the heap using **heappop()** method.

**heappop()**- It accepts heap as an input and returns root node element. It also recreates the heap after the root node is popped to make sure all nodes satisfy the heap property.

We are building on code from the last example in this example. We are first adding 10 numbers on the heap and then retrieving numbers one by one from the heap using **heappop()**. This returns us sorted elements.

```
import heapq
import random
random.seed(123)
heap = []
for i in range(10):
val = random.randint(1,10) + random.random()
heapq.heappush(heap, val)
print("Heap : {}\n".format(heap))
for i in range(10):
popped_element = heapq.heappop(heap)
print(popped_element)
```

As a part of our seventh example, we'll demonstrate how we can perform heap push and pop operation in a single method call using **heappushpop()** method.

**heappushpop()**- It accepts the heap and element to be pushed as input. It then pushes an element on the heap and then pops an element from the heap and returns it.

We are first creating a heap of 10 numbers. We are then looping 5 times, generating a random number between 1-20, pushing it on the heap, and popping an element from the heap. We are printing all these operations for tracking purposes as well.

```
import heapq
import random
random.seed(42)
heap = []
for i in range(10):
val = random.randint(1,10)
heapq.heappush(heap, val)
print("Heap : {}\n".format(heap))
for i in range(5):
print("Heap Initially : {}".format(heap))
val = random.randint(1, 20)
print("New value to be added : {}".format(val))
popped_elem = heapq.heappushpop(heap, val)
print("Popped Smallest Element : {}".format(popped_elem))
print("Heap after Push/Pop Ops : {}".format(heap))
```

As a part of our eighth example, we are demonstrating how we can pop an element from the heap and push the element on the heap in a single function call to **heapreplace()**.

**heapreplace()**- It takes as input a heap and an element that we want to push onto it. It then first pops an element from the heap and then pushes an element on the heap.

The code for this example is exactly the same as our previous example with the only change that we are using **heapreplace()** in this example instead of **heappushpop()**.

Please make a note that both this method can have different results even though both perform the same operations which we can notice if we compare the output of this example with the previous.

```
import heapq
import random
random.seed(42)
heap = []
for i in range(10):
val = random.randint(1,10)
heapq.heappush(heap, val)
print("Heap : {}\n".format(heap))
for i in range(5):
print("Heap Initially : {}".format(heap))
val = random.randint(1, 20)
print("New value to be added : {}".format(val))
popped_elem = heapq.heapreplace(heap, val)
print("Popped Smallest Element : {}".format(popped_elem))
print("Heap after Push/Pop Ops : {}".format(heap))
```

As a part of our ninth example, we'll explain how we can create a sorted list from a list of sorted lists using **merge()** method.

**merge(*iterables, key=None, reverse=False)**- It accepts a number of sorted lists and then sorts them all into one list. It has parameters named**key**and**reverse**which works exactly like Python's in-built**sorted()**method. The key accepts the lambda function which takes an individual element of the list and returns a value based on which sorting decision will be made. The**reverse**is a boolean value which if set to True will reverse sort the list.

Below we are creating five lists, each of length 5 which has random numbers in the range 1-50. We have kept all the lists sorted. We are then combining all lists using **merge()** method. We are then performing the same process and sorting all lists in reverse order.

Please make a note that in order to sort the list in reverse order, we need the original list also sorted in reverse order. Also, the method won't work on unsorted lists.

```
import heapq
import random
random.seed(123)
list1 = sorted([random.randint(1,50) for i in range(5)])
list2 = sorted([random.randint(1,50) for i in range(5)])
list3 = sorted([random.randint(1,50) for i in range(5)])
list4 = sorted([random.randint(1,50) for i in range(5)])
list5 = sorted([random.randint(1,50) for i in range(5)])
sorted_out = heapq.merge(list1, list2, list3, list4, list5)
print("Output : {}".format(sorted_out))
print("Output : {}".format(list(sorted_out)))
list1 = sorted([random.randint(1,50) for i in range(5)], reverse=True)
list2 = sorted([random.randint(1,50) for i in range(5)], reverse=True)
list3 = sorted([random.randint(1,50) for i in range(5)], reverse=True)
list4 = sorted([random.randint(1,50) for i in range(5)], reverse=True)
list5 = sorted([random.randint(1,50) for i in range(5)], reverse=True)
sorted_out2 = heapq.merge(list1, list2, list3, list4, list5, reverse=True)
print("Output : {}".format(list(sorted_out2)))
```

Our tenth example further explains the usage of **merge()** method on how to use its **key** parameter.

Our code this time creates lists where an individual element is a tuple of two-element. The first element in the tuple is a string and a second element is a random number in the range 1-50. We are sorting lists based on the second element of the tuple. We are then also reverse sorting lists and combining them.

```
import heapq
import random
random.seed(123)
list1 = sorted([(str(i), random.randint(1,50)) for i in range(5)], key=lambda x : x[1])
list2 = sorted([(str(i), random.randint(1,50)) for i in range(5)], key=lambda x : x[1])
list3 = sorted([(str(i), random.randint(1,50)) for i in range(5)], key=lambda x : x[1])
list4 = sorted([(str(i), random.randint(1,50)) for i in range(5)], key=lambda x : x[1])
list5 = sorted([(str(i), random.randint(1,50)) for i in range(5)], key=lambda x : x[1])
sorted_out = heapq.merge(list1, list2, list3, list4, list5, key=lambda x: x[1])
print("Output : {}".format(list(sorted_out)))
list1 = sorted([(str(i), random.randint(1,50)) for i in range(5)], reverse=True, key=lambda x : x[1])
list2 = sorted([(str(i), random.randint(1,50)) for i in range(5)], reverse=True, key=lambda x : x[1])
list3 = sorted([(str(i), random.randint(1,50)) for i in range(5)], reverse=True, key=lambda x : x[1])
list4 = sorted([(str(i), random.randint(1,50)) for i in range(5)], reverse=True, key=lambda x : x[1])
list5 = sorted([(str(i), random.randint(1,50)) for i in range(5)], reverse=True, key=lambda x : x[1])
sorted_out2 = heapq.merge(list1, list2, list3, list4, list5, key=lambda x: x[1], reverse=True)
print("\nOutput : {}".format(list(sorted_out2)))
```

As a part of our eleventh example, we are demonstrating how we can get n largest element from the list using **nlargest()** and n smallest element from the list using **nsmallest()** method.

**nlargest(n, iterable, key=None)**- It accepts a number and a list as input and returns that many largest elements from the list. If we have a list where an individual element is a tuple, list, or user-defined class instance then we can provide a lambda function specifying which attribute to use to get n largest elements.**nsmallest(n, iterable, key=None)**- It works exactly like**nlargest()**but returns n smallest elements.

Below we have explained the usage of both methods with a simple example.

```
import heapq
import random
random.seed(123)
list1 = [random.randint(1, 20) for i in range (20)]
print("List : {}\n".format(list1))
print("2 Largest Elements : {}".format(heapq.nlargest(2, list1)))
print("5 Largest Elements : {}\n".format(heapq.nlargest(5, list1)))
print("2 Smallest Elements : {}".format(heapq.nsmallest(2, list1)))
print("5 Smallest Elements : {}".format(heapq.nsmallest(5, list1)))
```

Our twelfth example further explains the usage of **nlargest()** and **nsmallest()** methods on the list where an individual element is a tuple of two elements. It returns the largest and smallest elements based on the 2nd value in the tuple.

```
import heapq
import random
random.seed(123)
list1 = [(str(i), random.randint(1, 20)) for i in range (20)]
print("List : {}\n".format(list1))
print("2 Largest Elements : {}".format(heapq.nlargest(2, list1, key=lambda x : x[1])))
print("5 Largest Elements : {}\n".format(heapq.nlargest(5, list1, key=lambda x : x[1])))
print("2 Smallest Elements : {}".format(heapq.nsmallest(2, list1, key=lambda x : x[1])))
print("5 Smallest Elements : {}".format(heapq.nsmallest(5, list1, key=lambda x : x[1])))
```

Our thirteenth and last example demonstrates how we can sort an array using **heapq** module methods. We are first creating a heap using **heappush()** method. We are then using **heapop()** method to get elements from the list in sorted order. This is how the heapsort algorithm works.

```
import heapq
import random
random.seed(123)
heap = []
for i in range(15):
val = random.randint(1,15)
heapq.heappush(heap, val)
print([heapq.heappop(heap) for i in range(15)])
```

This ends our small tutorial explaining the API provided by **heapq** module. Please feel free to let us know your views in the comments section.

When going through coding examples, it's quite common to have doubts and errors.

If you have doubts about some code examples or are stuck somewhere when trying our code, send us an email at **coderzcolumn07@gmail.com**. We'll help you or point you in the direction where you can find a solution to your problem.

You can even send us a mail if you are trying something new and need guidance regarding coding. We'll try to respond as soon as possible.

If you want to

- provide some suggestions on topic
- share your views
- include some details in tutorial
- suggest some new topics on which we should create tutorials/blogs