Heap in Python

Heap Python Module

The heap is used when you want to remove the highest or lowest order/priority elements. The heap allows quick access to these elements in O(1) time. However, the heap only provides quick access to the lowest or greatest elements; finding other elements takes O(n) time since the heap is not ordered (we must iterate through all the nodes).

You can read more about heap data structure here.

In Python, you have the heapq module, with which you can create a min heap or max heap. When you create a heap using the heapq function, by default, the heap will always be a min heap, meaning that each time the smallest element is popped from the heap.

The heapq module has some relevant functions to perform various operations on the heap data structure. These functions are given below:

• heapify: This function converts an iterable into a heap data structure, in-place, in linear time. After using this function, the heap's elements will be reordered so that it has the property of a min heap.
• heappush: This function inserts an element into a heap, and after insertion, the order is adjusted accordingly so that the heap structure is maintained. The help push function performs this operation in O(log(n)) time, where n is the size of the heap.
• heappop: This function removes and returns the smallest element of the heap, and after removal, the order is adjusted accordingly so that the heap structure is maintained. The heappop function performs this operation in O(log(n)) time, where n is the size of the heap.
• heappushpop: This function can push and pop elements into the heap. This function first pushes the provided element* to the heap and then pops the smallest element from the heap. The heappushpop function performs this operation in O(log(n)) time, where n is the size of the heap.
• heapreplace: This function also pushes and pops elements in the heap. But instead, it first pops the smallest element* from the heap and then *pushes the provided element back into the heap. The heapreplace function performs this operation in O(log(n)) time, where n is the size of the heap.
• nlargest: This function returns the k-largest elements from the heap. This function runs in O(log(k)) time, where k is the size parameter passed to the function.
• nsmallest: This function returns the k-smallest elements from the heap. This function runs in O(log(k)) time, where k is the size parameter passed to the function.

Creating a Heap in Python

In Python, the creation of a heap can be done by using the heapify function.

Code:

Output:

Explanation: In the above code, you can see that we pass the array to the heapify function and this function has brought the smallest element to the front as seen in the output.

Inserting into Heap

In Python, inserting elements into the heap can be done in many ways. Let's see how to insert elements into a heap.

Code:

Output:

Explanation: Above, you can see that we initialized an array with 5 elements and then converted the array into a heap using the heapify function. We use the append function to insert an element into a heap. The element will be added at the last index, and to make this array a heap again, we must heapify the array, so that all the elements are organized properly.

See the below code:

Output:

As seen in the output, after performing the heapify operation, the smallest element comes to the front.

But, since you are using Python, you don't have to append elements and heapify the whole array again and again. We will be using the help push function to insert elements into the heap.heappush function inserts an element into the heap and heapifies it.

Code:

Output:

Explanation: Above, you can see that we are inserting element 1 into the heap using the heappush function, and after insertion, the smallest element comes to the front, which means you don't have to perform the heapify operation again and again.

Removing Element From the Heap in Python

You can use the heappop function to remove the element from the heap. heappop function removes and returns the smallest element from the heap, which means it always removes the element at the first index.

Code:

Output:

Explanation: Above, you can see we use the heappop function to remove the smallest element from the heap. In our heap, 2 was the smallest element, so we removed it, and now the smallest element is 6. Element 6 will come to the 0th index as seen in the output.

Replacing an element in a Heap in Python

The heapreplace function is used to replace an element in a heap. This function removes the smallest element from the heap and inserts the new element at some location. If the element to be inserted is the smallest in the heap, then this element will be brought to the 0th index.

Code:

Output:

Explanation: Above you can see that at first the smallest element in the heap was 2. We perform the replace operation with element 10. After performing the replace operation, the smallest element of the heap(2) was replaced by element 10. Now the smallest element in the heap is 6, so it comes to the front of the heap.

Simultaneous Appending and Popping

Since we are using Python, we can simultaneously push and pop elements in the heap. Python provides two functions by which you can append and pop elements simultaneously from the heap. These functions are heappushpop and heapreplace. We have already discussed the heapreplace function. Now we will be discussing the heappushpop function.

Point to be noted:

The heappushpop function first pushes the provided element to the heap and then pops the smallest element from the heap, and the heapreplace function first pops the smallest element from the heap and then pushes the provided element back into the heap.

Example 1:

Code:

Output:

Explanation: At first, element 10 will be pushed into the heap, and after that, the smallest element in the heap will be popped out.

Example 2:

Code:

Output:

Explanation: Now you might be thinking, in the above output, why are both the heaps same? This is because, at first, the smallest element in the heap was 2, so it was in the 0th index. Now we use the heappushpop function to insert and delete elements from the heap. So this function first inserts element 1 into the heap. After that, the smallest element again comes to the 0th index and it will be removed.

See the below steps to know how the heappushpop function works.

• Initially, we have a heap, which means the smallest element will be at the 0th index.
• Now, when we use the heappushpop function,
  • It first inserts the provided element into the heap.
  • Perform the heapify operation so that the smallest element again comes at the front.
  • It removes the smallest element from the heap.

Using Heap to Find the Largest and the Smallest Element

We don’t need to sort the array to find k smallest or largest elements. We will be using some built-in functions that are present in the heapq module. These functions are the largest and smallest. The nlargest function returns the n-largest elements from the heap, and the nsmallest function returns the n-smallest elements from the heap.

Code:

Output:

Explanation: Above, you can see how we have found the two largest and smallest elements from the heap without using any sorting or any other techniques.

More about Heap in Python

Above, we have only discussed the min heap. When performing any operation, such as heapify,heappop, or heappush, we always say that the smallest element is present at the 0th index. What about the largest elements?

We will talk about the max heap in brief. max heap means the largest element will always be at the 0th index.

Let's say we have an array with five elements.

When we perform the heapify operation on the above array, the smallest element(2) will come at the front. This is a min-heap property. 

To implement max heap, just multiply every element by -1. By doing this, the largest element will become the smallest element, and it will come at the front.

Code:

Output:

Explanation: You can see that 8 was the largest element in the heap. After we change the sign, it becomes the smallest element and is brought to the front of the heap. Now, if we want to pop the largest element, then we will always get it at the 0th index. We can use the heappop function to pop the largest element from the heap and multiply that element with -1 so that it again converts to a positive.