How to convert min Heap to max Heap in Python

By Yatharth Jain

Heap is a binary tree data structure. In this type of data structure, the value at the root node is compared to the value of its children. This comparison gives rise to two different types of heaps. One is Max Heap and the other one is Min Heap.

Max Heap: A type of heap in which the value of the root node is either greater or equal to either of its children. That is if A has child node B then key(A) > key(B).  For example, Heap = [44, 35, 42, 26, 33, 19, 27, 10, 14, 31].

Min Heap: A type of heap in which the value of the root node is either smaller or equal to either of its children. That is if A has child node B then key(A) < key(B).  For example, Heap = [10, 14, 19, 26, 31, 42, 27, 44, 35, 33].

The problem in hand to convert a given min heap to the max heap using Python code. We will see this problem as one in which we have to build a max heap using an array of numbers. We will not be caring about the fact that the array is actually a min-heap. That is even if the given min-heap is an unsorted array our program will sort it to form a max heap. We will start from the last child of the mean heap and go in the reverse direction to form the max heap.

The Python code for conversion of min-heap to the max heap is given below.

Convert min Heap to max Heap in Python

#python3 program to convert min heap to max heap  
  
#Building max heap  
def MaxHeap(heap,l): 
#Starting from the last node and going till first node
    for i in range((l-2)//2,-1,-1): 
        maxheap(heap,i,l)

#printing array 
def printheap(heap,s): 
    for k in range(s): 
        print(heap[k],end=" ") 
    print()

#to arrange the node in a heap 
def maxheap(heap,i,l): 
    L=2*i+1
    j=2*i+2
    biggest=i
    if L<l and heap[L]>heap[i]:  
        biggest=L
    if j<l and heap[j]>heap[biggest]:  
        biggest=j
    if biggest!=i: 
        heap[i],heap[biggest]=heap[biggest],heap[i]  
        maxheap(heap,biggest,l) 

#Driver Code  
#given min heap 
heap=[10,14,19,26,31,42,27,44,35,33]  
l=len(heap) 
  
print("Given Min Heap: ")  
printheap(heap,l)  

#Converting min heap to max heap
MaxHeap(heap,l)  
  
print("Converted max heap: ")  
printheap(heap,l)

print("Code By: Yatharth Jain")

OUTPUT:

Given Min Heap: 
10 14 19 26 31 42 27 44 35 33 
Converted max heap: 
44 35 42 26 33 19 27 10 14 31 
Code By: Yatharth Jain

The time complexity of the given code is O(n). I have used the same example in the code as I used to explain min heap and max heap. But the code is valid for any example of the user’s choice.

More To Read:

1. How to Count maximum points on same line in Python
2. Diagonal traversal of a binary tree in Python