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.
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.
