# Python heap implementation using heapq module

In this post, you will know the heap queue implementation in **Python** using the **heapq** module with several operations. This module uses the binary heap data structure and create heap using a regular Python list. Before using this module, you should recall the priority queue and head sort.

## Priority Queue

This module gives us a brisk and simple approach to built any sort of **priority queue** for your application. The elements in priority queue have some priority. The priority of the element is used to determine the order in which the elements will be processed. The element with the highest priority is processed first. This is very useful data structure, basically used in all scheduling kind of processes.

## Heap Sort

In **Heap Sort**, we are using Binary Search Tree for sorting. In this, all elements are inserted into tree. Heap sort requires more space than other sorting methods. It is stable sort and requires constant space for sorting. The heap tree can be of two types - Max Tree and Min Tree.

**Max Tree -**The root node has highest key value, then the child node elements.**Min Tree -**The root node has lowest key value, then the child node elements.

**Heap sort** basically works in two phases. Suppose an array **A** has **n** elements, it sorts the array in two phases.

- First build a heap from elements of the array.
- In the second phase, it repeatedly deletes the root element from the heap that built in the first phase and place the element in the last empty location of the array.

## Heapq Module

The **Heapq** is a **Python** module which gives an implementation of the min heap. It utilizes binary search and opens several functions to implement a priority queue. This module is pre-installed with Python, so there is no need to install it separately using pip. This module may solve many programming issues, like, to find the largest numbers from a list of integers or to find the smallest numbers from the list in Python.

### Import heapq module

First, we need to import this using the following command -

**import heapq**

### Python heapq example

Here is the simple example of Python **heapq** module to find three largest numbers and three smallest numbers from the list.

```
import heapq as hq
lists = [19, 39, 78, 29, 52, 11, 23]
# Get three largest values
largest_values = hq.nlargest(3, lists)
# Get three smallest values
smallest_values = hq.nsmallest(3, lists)
print("Three largest numbers are: ", largest_values)
print("Three smallest numbers are: ", smallest_values)
```

**Output of the above code -**

```
Three largest numbers are: [78, 52, 39]
Three smallest numbers are: [11, 19, 23]
```

## Python Heapq Function

The **heapq** module of **Python** has some methods that implement heap operations on lists. These are the following methods -

### heappush()

The **heappush()** method is used to push elements to the heap. The syntax is -

**hq.heappush(heap, element)**

Here, we have mentioned the example of **heappush()** method -

```
import heapq as hq
heap_elems = [19, 39, 78, 29, 52, 11, 23]
print("The elements of head are: ",end="")
print (list(heap_elems))
# push elements into heap
hq.heappush(heap_elems, 33)
print("The modified heap after push is : ",end="")
print (list(heap_elems))
```

**Output of the above code -**

```
The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after push is : [19, 39, 78, 29, 52, 11, 23, 33]
```

### heappop()

The Python **heapq** module defines **heappop()** method to pop the smallest element while protecting the heap property. The syntax is -

**heappop(heap)**

Here, we have mentioned the example of **heappop()** method -

```
import heapq as hq
heap_elems = [19, 39, 78, 29, 52, 11, 23]
print("The elements of head are: ",end="")
print (list(heap_elems))
# pop elements into heap
hq.heappop(heap_elems)
print("The modified heap after pop is : ",end="")
print(list(heap_elems))
```

**Output of the above code -**

```
The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after pop is : [23, 39, 78, 29, 52, 11]
```

### heappushpop()

The **heappushpop()** method is equivalent to **heappush()** followed by **heappop()**. The syntax of **heappushpop()** is -

**heappushpop(heap)**

Here is the example of **heappushpop()** -

```
import heapq as hq
heap_elems = [19, 39, 78, 29, 52, 11, 23]
print("The elements of head are: ",end="")
print(list(heap_elems))
hq.heappushpop(heap_elems)
print("The modified heap is : ",end="")
print(list(heap_elems))
```

**Output of the above code -**

```
The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after push pop is : 19
[23, 39, 78, 29, 52, 11, 23]
```

### heapify()

This function **heapify()** accepts an arbitrary list and converts it to a heap. The syntax of **heapify()** is -

```
import heapq as hq
heap_elems = [19, 39, 78, 29, 52, 11, 23]
print("The elements of head are: ",end="")
print(list(heap_elems))
# convert elements into heap
hq.heapify(heap_elems)
print("The heap is : ",end="")
print(list(heap_elems))
```

**Output of the above code -**

```
The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The heap is : [11, 29, 19, 39, 52, 78, 23]
```

### heapreplace()

It erases the smallest element from the heap and then inserts a new item. This function is more efficient than calling **heappop()** and **heappush()**. The syntax of **heapreplace()** is -

**heapreplace(heap, element)**

Here is the example of **heapreplace()** -

```
import heapq as hq
heap_elems = [19, 39, 78, 29, 52, 11, 23]
print("The elements of head are: ",end="")
print(list(heap_elems))
hq.heapreplace(heap_elems, 20 )
print("The modified heap after heapreplace is : ",end="")
print(heap_elems )
```

**Output of the above code -**

```
The elements of head are: [19, 39, 78, 29, 52, 11, 23]
The modified heap after heapreplace is : [20, 39, 78, 29, 52, 11, 23]
```

### Related Articles

**range and xrange in Python2d arrays in Pythonsplitlines in pythonSimple Calculator Program in Pythonstrip function in Pythoncasefold in PythonPrime factors of a number in PythonPython nonlocal keywordGreatest common divisor Python recursive Python String isalpha() Method Program to print ASCII Value of a character Python program to sort words in alphabetical order *args and **kwargs in Python Printing Simple Diamond Pattern in Python Stemming and Lemmatization in Python Python | Generate QR Code using pyqrcode module**