heapq - Heap Queue/Priority Queue Implementation in Python¶

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.

Example 1¶

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.

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

Example 2¶

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.

Example 3¶

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

Example 4¶

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

Heap

               A
          C         B
       R     D     E   Z
     S   T  F  G

Example 5¶

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.

Example 6¶

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.

Example 7¶

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.

Example 8¶

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.

Example 9¶

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.

Example 10¶

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.

Example 11¶

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.

Example 12¶

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.

Example 13¶

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.

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.