Heap using Python

Heap is a specialized tree-based data structure and is used to represent the priority queue. In the heap-sort algorithm, we have two heaps min-heap and max-heap.

Let’s take the input as [6,8,9,2,4]

(i) Min-heap:
In the Min-heap, the “Parent node should be less than or equal to the child node”. Let’s arrange the input as in the tree structure.

Fig-Input

In this input, “8 and 9” are the child nodes of a parent node “6” and the parent node 6 satisfy the condition. “2 and 4” are the child nodes of a parent node “8” but the parent node 8 does not satisfy the condition. So, we have to swap 8 and 2 and it is shown in Img 1.

Note: The condition is Parent node should be less than or equal to the child node.

Now, “2 and 9” are the child nodes of a parent node “6” and the parent node 6 does not satisfy the condition. So, we have to swap 6 and 2 and it is shown in Img 2.
Next, “8 and 4” are the child nodes of a parent node “6” and the parent node 6 does not satisfy the condition. So, we have to swap 6 and 4 and it is shown in Img 3.

In Img 3, “4 and 9” are the child nodes of a parent node “2” and the parent node 2 satisfy the condition & “8 and 6” are the child nodes of a parent node “4” and the parent node 4 satisfy the condition. Finally, we formed the min-heap structure.

For the input [6,8,9,2,4], the output min-heap is [2,4,9,8,6].

(ii) Max-heap:

In the Max-heap, the “Parent node should be greater than or equal to the child node”. Fig-Input represents the same input tree structure.

In Img 4, “8 and 9” are the child nodes of a parent node “6” and the parent node 6 does not satisfy the condition so, we have to swap 6 and 9 and it is shown in Img 5.

Note: The Max-heap condition is Parent node should be greater than or equal to the child node.

In Img 5, “8 and 6” are the child nodes of a parent node “9” and the parent node 9 satisfy the condition & “2 and 4” are the child nodes of a parent node “8” and the parent node 8 satisfy the condition. Finally, we formed the max-heap structure.

For the input [6,8,9,2,4], the output min-heap is [9,8,6,2,4].

Implementation of Heap:

In python, the heapq module is used to implement a heap data structure. Mainly this module represents the min-heap type.

(i) heapify(input):

It is used to convert the input list into a min-heap data structure.

• Import heapq module.
• let’s take the input as [6,8,9,2,4].
• Heapify function converts the input into the min-heap structure.

Output:

(ii) heappush(input,element):

It is used to insert the element in the heap and also maintaining the heap structure.

• Now, the heap structure will be [2,4,9,8,6].
• Add element “5” in heap structure using heappush function.

Output:

(iii) heappop(input):

It is used to remove the smallest element in the heap structure and also maintaining the heap structure.

• Now, the new heap structure will be [2,4,5,8,6,9].
• By using heappop, we can remove the smallest element from the heap.

Output:

(iv) heappushpop(input,element):

This function represents the combination of both push and pop functions. In this, the given element is first pushed, then the smallest element is poped.

• Let’s take the input as [6,8,9,3,4].
• Heapify function converts the input into the min-heap structure [3,4,9,8,6].
• Heappushpop function adds an element “2” and deletes the smallest element in heap structure “2”.

Output:

(v) heapreplace(input,element):

This function also inserts and deletes the element but it is different when compare to heappushpop. In this heapreplace, the smallest element is first popped, then the element is pushed.

• Let’s take the same input as [6,8,9,3,4].
• Heapify function converts the input into the min-heap structure [3,4,9,8,6].
• Heapreplace function deletes the smallest element first “2” and adds a new element “2”. Here the poped element is “3”.

Output:

(vi) nsmallest(k,input):

It returns the k smallest elements. Ex: nsmallest(k,input)

• Let’s take the same input as [6,8,9,3,4].
• Heapify function converts the input into the min-heap structure [3,4,9,8,6].
• nsmallest(2, input) function returns the two smallest elements [3,4].

Output:

(vii) nlargest(k,input):

It returns the k largest elements. Ex: nlargest(k,input)

• Let’s take the same input as [6,8,9,3,4].
• Heapify function converts the input into the min-heap structure [3,4,9,8,6].
• nlargest(2, input) function returns the two largest elements [9,8].

Output:

Thank you.