How to merge two binary max heaps in Python

In this tutorial, we will see what is max heap and how to merge two binary max heaps in Python.

The answer of our first question, a max heap is a complete binary tree in which the value node is greater than its children.

We are assuming the binary max heaps as arrays for better understanding. To map the heap elements in an array, we store the node at index “i” and its left and right child at index “2i+1” and “2i+2” respectively.

Now consider two binary max heaps given below

After merging this heap we get the following max heap as output

Merging two binary max heaps in Python

We consider two binary max heaps in the form of arrays and store the merged max heap in an array.

Following is the code to merge the binary max-heap in Python.

# Builds a Max heap of given arr[0..n-1] 
def buildMaxHeap(arr, n): 

    # building the heap from first non-leaf 
    # node by calling Max heapify function 
    for i in range(int(n / 2) - 1, -1, -1): 
        MaxHeapify(arr, n, i) 
        
def MaxHeapify(arr, n, index): 

    # Find largest of node and 
    # its children 
    if index >= n: 
        return
    left_child = 2 * index + 1
    right_child = 2 * index + 2
    Max = 0
    if left_child < n and arr[left_child] > arr[index]: 
        Max = left_child 
    else: 
        Max = index 
    if right_child < n and arr[right_child] > arr[Max]: 
        Max = right_child 

    # Put Maximum value at root and 
    # recur for the child with the 
    # Maximum value 
    if Max != index: 
        arr[Max], arr[index] = arr[index], arr[Max] 
        MaxHeapify(arr, n, Max)

# Function to Merge Max heaps heap1[] and heap2[] into merged_heap[] 
def mergeHeaps(merged_heap, heap1, heap2, len1, len2): 

    # Copy elements of heap1[] and heap2[] to merged_heap[] 
    for i in range(len1): 
        merged_heap[i] = heap1[i] 
    for i in range(len2): 
        merged_heap[len1 + i] = heap2[i] 

    # build heap for the modified 
    # array of size len1+len2 
    buildMaxHeap(merged_heap, len1 + len2) 

    
# Driver code 
 
heap1 = [20, 17, 15, 10] 
heap2 = [19, 13, 7] 

len1 = len(heap1) 
len2 = len(heap2) 

merged_heap = [0] * (len1 + len2) 
mergeHeaps(merged_heap, heap1, heap2, len1, len2) 

print("Merged Binary Max Heap is")

for i in range(len1 + len2): 
    print(merged_heap[i], end = " ") 

OUTPUT:

Merged Binary Max Heap is

20 19 15 10 17 13 7

Time Complexity of the above program is:

1.  O(n) for building the heap from an array of n elements.
2. The complexity of merging the heaps is equal to O( len1 + len2 ).