Given two binary max heaps as arrays, merge the given heaps to form a new max heap.
 
Example 1:
Input  : 
n = 4 m = 3
a[] = {10, 5, 6, 2}, 
b[] = {12, 7, 9}
Output : 
{12, 10, 9, 2, 5, 7, 6}
Explanation :
 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function mergeHeaps() which takes the array a[], b[], its size n and m, as inputs and return the merged max heap. Since there can be multiple solutions, therefore, to check for the correctness of your solution, your answer will be checked by the driver code and will return 1 if it is correct, else it returns 0.
 
Expected Time Complexity: O(n.Logn)
Expected Auxiliary Space: O(n + m)
 
Constraints:
1 <= n, m <= 10^{5}
1 <= a[i], b[i] <= 2*10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution():
    def mergeHeaps(self, a, b, n, m):
        #your code here

Solutions:
import heapq

def heapify(heap, n, i):
	largest = i
	left = 2 * i + 1
	right = 2 * i + 2
	if left < n and heap[left] > heap[largest]:
		largest = left
	if right < n and heap[right] > heap[largest]:
		largest = right
	if largest != i:
		(heap[i], heap[largest]) = (heap[largest], heap[i])
		heapify(heap, n, largest)

class Solution:

	def mergeHeaps(self, a, b, n, m):
		merged = a + b
		k = len(merged)
		for i in range(k // 2 - 1, -1, -1):
			heapify(merged, k, i)
		return merged


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		list1 = []
		for i in a:
			heapq.heappush(list1, -i)
		for j in b:
			heapq.heappush(list1, -j)
		heap = []
		for i in list1:
			heap.append(-i)
		return heap


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		list1 = a + b
		list1.sort()
		return list1[::-1]


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		merged = []
		for i in a:
			heapq.heappush(merged, -i)
		for i in b:
			heapq.heappush(merged, -i)
		res = []
		for i in merged:
			res.append(-i)
		return res


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		h = []
		for i in a:
			heapq.heappush(h, i * -1)
		for i in b:
			heapq.heappush(h, i * -1)
		res = []
		while h:
			res.append(heapq.heappop(h) * -1)
		return res


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		l = a + b
		t = []
		for i in range(len(l)):
			l[i] *= -1
		heapq.heapify(l)
		for i in range(len(l)):
			t.append(-l[i])
		return t


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		max_heap = []
		for num in a:
			heapq.heappush(max_heap, -num)
		for num in b:
			heapq.heappush(max_heap, -num)
		max_heap = [-num for num in max_heap]
		return max_heap


class Solution:

	def mergeHeaps(self, a, b, n, m):
		c = a + b
		c.sort()
		c = c[::-1]
		return c


class Solution:

	def MaxHeapify(self, arr, N, idx):
		if idx >= N:
			return
		l = 2 * idx + 1
		r = 2 * idx + 2
		Max = 0
		if l < N and arr[l] > arr[idx]:
			Max = l
		else:
			Max = idx
		if r < N and arr[r] > arr[Max]:
			Max = r
		if Max != idx:
			(arr[Max], arr[idx]) = (arr[idx], arr[Max])
			self.MaxHeapify(arr, N, Max)

	def buildMaxHeap(self, arr, N):
		for i in range(int(N / 2) - 1, -1, -1):
			self.MaxHeapify(arr, N, i)

	def mergeHeaps(self, a, b, N, M):
		merged = [0] * (N + M)
		for i in range(N):
			merged[i] = a[i]
		for i in range(M):
			merged[N + i] = b[i]
		self.buildMaxHeap(merged, N + M)
		return merged


def heapify_max_heap(heap_arr: [], n: int, index: int):
	largest = index
	left_index = 2 * index + 1
	right_index = 2 * index + 2
	if left_index < n and heap_arr[largest] < heap_arr[left_index]:
		largest = left_index
	if right_index < n and heap_arr[largest] < heap_arr[right_index]:
		largest = right_index
	if largest != index:
		(heap_arr[largest], heap_arr[index]) = (heap_arr[index], heap_arr[largest])
		heapify_max_heap(heap_arr, n, largest)

def merge_two_binary_heaps(heap_arr1: [], heap_arr2: [], n: int, m: int):
	heap_arr1.extend(heap_arr2)
	extend = (n + m) // 2
	for i in reversed(range(extend)):
		heapify_max_heap(heap_arr1, n + m, i)
	return heap_arr1

class Solution:

	def mergeHeaps(self, a, b, n, m):
		return merge_two_binary_heaps(a, b, n, m)


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		arr3 = []
		for i in a + b:
			heapq.heappush(arr3, -i)
		for (index, val) in enumerate(arr3):
			arr3[index] = -val
		return arr3


class Solution:

	def heapify(self, a, n, i):
		parent = i
		lchild = 2 * i + 1
		rchild = 2 * i + 2
		if lchild <= n - 1 and a[lchild] > a[parent]:
			parent = lchild
		if rchild <= n - 1 and a[rchild] > a[parent]:
			parent = rchild
		if i != parent:
			(a[parent], a[i]) = (a[i], a[parent])
			self.heapify(a, n, parent)

	def mergeHeaps(self, a, b, n, m):
		a += b
		for i in range(int(len(a) / 2 - 1), -1, -1):
			self.heapify(a, len(a), i)
		return a


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		a += b
		h = []
		heapq.heapify(h)
		for i in a:
			heapq.heappush(h, -i)
		k = []
		for i in h:
			k.append(-i)
		return k


import heapq

class Solution:

	def mergeHeaps(self, a, b, n, m):
		l = []
		for i in a:
			heapq.heappush(l, -i)
		for i in b:
			heapq.heappush(l, -i)
		ans = []
		for i in l:
			ans.append(-i)
		return ans


from heapq import *

class Solution:

	def mergeHeaps(self, a, b, n, m):
		heap = a + b
		heap = [-1 * elm for elm in heap]
		heapify(heap)
		heap = [-1 * elm for elm in heap]
		return heap


from heapq import *

class Solution:

	def mergeHeaps(self, a, b, n, m):
		heap = a + b
		heap = list(map(lambda x: -x, heap))
		heapify(heap)
		heap = list(map(lambda x: -x, heap))
		return heap


from heapq import *

class Solution:

	def mergeHeaps(self, a, b, n, m):
		a += b
		for i in range(n + m):
			a[i] *= -1
		heapify(a)
		for i in range(n + m):
			a[i] *= -1
		return a