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 “
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 =  * (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 = " ")
Merged Binary Max Heap is 20 19 15 10 17 13 7
Time Complexity of the above program is:
- O(n) for building the heap from an array of n elements.
- The complexity of merging the heaps is equal to O( len1 + len2 ).