# Python heap implementation using heapq module

In this post, you will learn about the heap queue implementation in **Python** using the **heapq** module with several operations. This module uses the binary heap data structure and creates a 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 the 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 a very useful data structure, basically used in all kinds of scheduling processes.

## Heap Sort

In **Heap Sort**, we are using a Binary Search Tree for sorting. In this, all elements are inserted into a tree. Heap sort requires more space than other sorting methods. It is a 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 the highest key value, then the child node elements.**Min Tree-**The root node has the 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 the elements of the array.
- In the second phase, it repeatedly deletes the root element from the heap that was built in the first phase and place the element in the last empty location of the array.

## Python 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 the **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 the **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 the **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

**
Python program to sum all the numbers in a list
Difference between tuple and list in Python
Alphabetical order Python
Write a program to read two numbers and print their quotient and remainder in python
ASCII value in Python
Greatest common divisor (GCD) in Python
Python nonlocal keyword
Prime factor Python
casefold in Python
strip function in Python
Convert array to list Python
Remove element from list Python
Convert list to dictionary Python
Python dict inside list
Convert list to string Python
Remove last element from list Python
Convert string to list Python
Python add list to list
Difference between tuple and list in Python
Alphabetical order Python
**