Given an input stream of N integers. The task is to insert these numbers into a new stream and find the median of the stream formed by each insertion of X to the new stream.
Example 1:
Input:
N = 4
X[] = 5,15,1,3
Output:
5
10
5
4
Explanation:Flow in stream : 5, 15, 1, 3 
5 goes to stream --> median 5 (5) 
15 goes to stream --> median 10 (5,15) 
1 goes to stream --> median 5 (5,15,1) 
3 goes to stream --> median 4 (5,15,1 3) 
 
Example 2:
Input:
N = 3
X[] = 5,10,15
Output:
5
7.5
10
Explanation:Flow in stream : 5, 10, 15
5 goes to stream --> median 5 (5) 
10 goes to stream --> median 7.5 (5,10) 
15 goes to stream --> median 10 (5,10,15) 
Your Task:
You are required to complete the class Solution. 
It should have 2 data members to represent 2 heaps. 
It should have the following member functions:
	insertHeap() which takes x as input and inserts it into the heap, the function should then call balanceHeaps() to balance the new heap.
	balanceHeaps() does not take any arguments. It is supposed to balance the two heaps.
	getMedian() does not take any arguments. It should return the current median of the stream.
Expected Time Complexity : O(nlogn)
Expected Auxilliary Space : O(n)
 
Constraints:
1 <= N <= 10^{6}
1 <= x <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3

''' 
use globals min_heap and max_heap, as per declared in driver code
use heapify modules , already imported by driver code
'''

class Solution:
    def balanceHeaps(self):
        #Balance the two heaps size , such that difference is not more than one.
        # code here
        
        
    '''    
    You don't need to call getMedian it will be called itself by driver code
    for more info see drivers code below.
    '''
    def getMedian(self):
        # return the median of the data received till now.
        # code here
        
        
    def insertHeaps(self,x):
        #:param x: value to be inserted
        #:return: None
        # code here

Solutions:
import heapq

class Solution:

	def __init__(self):
		self.maxHeap = []
		self.minHeap = []

	def balanceHeaps(self):
		if len(self.maxHeap) > len(self.minHeap) + 1:
			heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
		elif len(self.minHeap) > len(self.maxHeap):
			heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

	def getMedian(self):
		if len(self.maxHeap) == len(self.minHeap):
			return (-self.maxHeap[0] + self.minHeap[0]) / 2
		else:
			return -self.maxHeap[0]

	def insertHeaps(self, num):
		if not self.maxHeap or num < -self.maxHeap[0]:
			heapq.heappush(self.maxHeap, -num)
		else:
			heapq.heappush(self.minHeap, num)
		self.balanceHeaps()


class Solution:
	left = []
	right = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.left) == len(self.right):
			return (-self.left[0] + self.right[0]) // 2
		if len(self.left) > len(self.right):
			return -self.left[0]
		return self.right[0]

	def insertHeaps(self, x):
		heapq.heappush(self.right, x)
		if self.left and self.right[0] < -self.left[0]:
			heapq.heappush(self.left, -heapq.heappop(self.right))
		if len(self.left) - len(self.right) > 1:
			heapq.heappush(self.right, -heapq.heappop(self.left))
		elif len(self.right) - len(self.left) > 1:
			heapq.heappush(self.left, -heapq.heappop(self.right))


import heapq

class Solution:

	def __init__(self):
		(self.large, self.small) = ([], [])

	def balanceHeaps(self):
		if len(self.small) - len(self.large) > 1:
			heapq.heappush(self.large, -heapq.heappop(self.small))
		elif len(self.large) - len(self.small) > 1:
			heapq.heappush(self.small, -heapq.heappop(self.large))

	def getMedian(self):
		if len(self.small) > len(self.large):
			return -self.small[0]
		elif len(self.large) > len(self.small):
			return self.large[0]
		else:
			return (self.large[0] - self.small[0]) / 2.0

	def insertHeaps(self, x):
		if len(self.small) == 0 or -self.small[0] >= x:
			heapq.heappush(self.small, -x)
		else:
			heapq.heappush(self.large, x)
		self.balanceHeaps()


class Solution:

	def __init__(self):
		(self.small, self.large) = ([], [])

	def balanceHeaps(self):
		if self.small and self.large and (-self.small[0] > self.large[0]):
			val = -heapq.heappop(self.small)
			heapq.heappush(self.large, val)
		if len(self.small) - len(self.large) > 1:
			val = -heapq.heappop(self.small)
			heapq.heappush(self.large, val)
		elif len(self.large) - len(self.small) > 1:
			val = -heapq.heappop(self.large)
			heapq.heappush(self.small, val)

	def getMedian(self):
		if len(self.small) > len(self.large):
			return -self.small[0]
		elif len(self.small) < len(self.large):
			return self.large[0]
		else:
			return (-1 * self.small[0] + self.large[0]) / 2

	def insertHeaps(self, x):
		heapq.heappush(self.small, -x)
		self.balanceHeaps()


def heapify_up(arr, n):
	if n <= 0:
		return
	if n & 1 == 0:
		parent = n // 2 - 1
	else:
		parent = n // 2
	if arr[parent] > arr[n]:
		(arr[parent], arr[n]) = (arr[n], arr[parent])
		heapify_up(arr, parent)

def heapify_up_max(arr, n):
	if n <= 0:
		return
	if n & 1 == 0:
		parent = n // 2 - 1
	else:
		parent = n // 2
	if arr[parent] < arr[n]:
		(arr[parent], arr[n]) = (arr[n], arr[parent])
		heapify_up_max(arr, parent)

def heapify_down_min(arr, k, n):
	lchild = 2 * k + 1
	rchild = 2 * k + 2
	index = k
	if k >= n or lchild >= n:
		return
	if lchild < n and arr[lchild] < arr[index]:
		index = lchild
	if rchild < n and arr[rchild] < arr[index]:
		index = rchild
	if k != index:
		(arr[k], arr[index]) = (arr[index], arr[k])
		heapify_down_min(arr, index, n)

def heapify_down_max(arr, k, n):
	lchild = 2 * k + 1
	rchild = 2 * k + 2
	index = k
	if k >= n or lchild >= n:
		return
	if lchild < n and arr[lchild] > arr[index]:
		index = lchild
	if rchild < n and arr[rchild] > arr[index]:
		index = rchild
	if k != index:
		(arr[k], arr[index]) = (arr[index], arr[k])
		heapify_down_max(arr, index, n)

def delete_min(arr, n):
	if n <= 1:
		arr.pop(0)
		return
	else:
		arr[0] = arr[n - 1]
		arr.pop(n - 1)
		n -= 1
		heapify_down_min(arr, 0, n)

def delete_max(arr, n):
	if n <= 1:
		arr.pop(0)
		return
	else:
		arr[0] = arr[n - 1]
		arr.pop(n - 1)
		n -= 1
		heapify_down_max(arr, 0, n)

class Solution:

	def __init__(self):
		self.max_heap = []
		self.min_heap = []
		self.count = 0
		self.flag = 0

	def balanceHeaps(self):
		l_max = len(self.max_heap)
		l_min = len(self.min_heap)
		while l_min > l_max:
			x = self.min_heap[0]
			delete_min(self.min_heap, l_min)
			l_min -= 1
			self.max_heap.append(x)
			heapify_up_max(self.max_heap, l_max)
			l_max += 1
		while l_max - l_min > 1:
			x = self.max_heap[0]
			delete_max(self.max_heap, l_max)
			l_max -= 1
			self.min_heap.append(x)
			heapify_up(self.min_heap, l_min)
			l_min += 1

	def getMedian(self):
		if self.count & 1 == 1:
			return self.max_heap[0]
		else:
			return (self.max_heap[0] + self.min_heap[0]) / 2

	def insertHeaps(self, x):
		l_max = len(self.max_heap)
		l_min = len(self.min_heap)
		if l_max > 0:
			top = self.max_heap[0]
			if x > top:
				self.min_heap.append(x)
				heapify_up(self.min_heap, l_min)
				l_min += 1
			else:
				self.max_heap.append(x)
				heapify_up_max(self.max_heap, l_max)
				l_max += 1
		else:
			self.max_heap.append(x)
			heapify_up_max(self.max_heap, l_max)
			l_max += 1
		self.count += 1
		if l_max - l_min > 1 or l_min > l_max:
			self.balanceHeaps()


import heapq

class Solution:

	def __init__(self):
		self.g = []
		self.s = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.g) > len(self.s):
			heapq.heappush(self.s, -heapq.heappop(self.g))
		if len(self.g) != len(self.s):
			return -self.s[0]
		else:
			return (self.g[0] - self.s[0]) / 2

	def insertHeaps(self, x):
		heapq.heappush(self.s, -x)
		heapq.heappush(self.g, -heapq.heappop(self.s))


import heapq as hq

class Solution:

	def __init__(self):
		(self.small, self.large) = ([], [])

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.small) > len(self.large):
			return -1 * self.small[0]
		if len(self.large) > len(self.small):
			return self.large[0]
		return (-1 * self.small[0] + self.large[0]) / 2

	def insertHeaps(self, num):
		hq.heappush(self.small, -1 * num)
		if self.small and self.large and (-1 * self.small[0] > self.large[0]):
			val = -1 * hq.heappop(self.small)
			hq.heappush(self.large, val)
		if len(self.small) > len(self.large) + 1:
			val = -1 * hq.heappop(self.small)
			hq.heappush(self.large, val)
		if len(self.large) > len(self.small) + 1:
			val = hq.heappop(self.large)
			hq.heappush(self.small, -1 * val)


class Solution:

	def __init__(self):
		self.s = []
		self.g = []

	def balanceHeaps(self):
		c = 0

	def getMedian(self):
		if len(self.g) == len(self.s):
			return (self.g[0] - self.s[0]) / 2
		elif len(self.s) > len(self.g):
			return -self.s[0]
		else:
			return self.g[0]

	def insertHeaps(self, x):
		from heapq import heappush, heappop
		if not self.s or -self.s[0] > x:
			heappush(self.s, -x)
		else:
			heappush(self.g, x)
		if len(self.s) > len(self.g) + 1:
			heappush(self.g, -heappop(self.s))
		elif len(self.g) > len(self.s) + 1:
			heappush(self.s, -heappop(self.g))


from heapq import heapify, heappop, heappush
min_heap = []
max_heap = []
min_num = 0
max_num = 0

class Solution:

	def balanceHeaps(self):
		global max_heap, min_heap, min_num, max_num
		while abs(min_num - max_num) > 1:
			if max_num - min_num > 1:
				heappush(min_heap, -1 * heappop(max_heap))
				max_num -= 1
				min_num += 1
			elif min_num - max_num > 1:
				heappush(max_heap, -1 * heappop(min_heap))
				min_num -= 1
				max_num += 1
		return

	def getMedian(self):
		global max_heap, min_heap, min_num, max_num
		if min_num + max_num == 0:
			return
		if min_num > max_num:
			return min_heap[0]
		elif max_num > min_num:
			return -1 * max_heap[0]
		else:
			return (-1 * max_heap[0] + min_heap[0]) / 2

	def insertHeaps(self, x):
		global max_heap, min_heap, min_num, max_num
		if min_num == 0:
			min_heap.append(x)
			min_num += 1
		elif max_num == 0:
			max_num += 1
			if min_heap[0] > x:
				max_heap.append(-1 * x)
			else:
				max_heap.append(-1 * min_heap.pop())
				min_heap.append(x)
		elif -1 * max_heap[0] > x:
			heappush(max_heap, -1 * x)
			max_num += 1
		else:
			heappush(min_heap, x)
			min_num += 1
		self.balanceHeaps()
		return


class Solution:

	def __init__(self):
		(self.minh, self.maxh) = ([], [])
		heapq.heapify(self.minh)
		heapq.heapify(self.maxh)

	def balanceHeaps(self):
		if len(self.maxh) > len(self.minh) + 1:
			heapq.heappush(self.minh, -heapq.heappop(self.maxh))
		elif len(self.minh) > len(self.maxh) + 1:
			heapq.heappush(self.maxh, -heapq.heappop(self.minh))

	def getMedian(self):
		if len(self.maxh) > len(self.minh):
			mx = heapq.heappop(self.maxh)
			heapq.heappush(self.maxh, mx)
			return -mx
		elif len(self.minh) > len(self.maxh):
			mn = heapq.heappop(self.minh)
			heapq.heappush(self.minh, mn)
			return mn
		else:
			mx = heapq.heappop(self.maxh)
			mn = heapq.heappop(self.minh)
			heapq.heappush(self.maxh, mx)
			heapq.heappush(self.minh, mn)
			return (mn - mx) / 2

	def insertHeaps(self, x):
		if len(self.maxh) == 0 or self.maxh[0] < -x:
			heapq.heappush(self.maxh, -x)
		else:
			heapq.heappush(self.minh, x)
		self.balanceHeaps()


import statistics

class Solution:
	lo = []
	hi = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.lo) > len(self.hi):
			return -self.lo[0]
		else:
			return (self.hi[0] - self.lo[0]) / 2

	def insertHeaps(self, x):
		heapq.heappush(self.lo, -x)
		heapq.heappush(self.hi, -self.lo[0])
		heapq.heappop(self.lo)
		if len(self.lo) < len(self.hi):
			heapq.heappush(self.lo, -self.hi[0])
			heapq.heappop(self.hi)


min_heap = []
heapq.heapify(min_heap)
max_heap = []
heapq.heapify(max_heap)

class Solution:

	def balanceHeaps(self):
		while len(max_heap) > len(min_heap) + 1:
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
			return
		while len(max_heap) + 1 < len(min_heap):
			heapq.heappush(max_heap, -heapq.heappop(min_heap))
			return
		return

	def getMedian(self):
		if len(min_heap) == len(max_heap):
			if len(min_heap) == 0:
				return 0
			return (min_heap[0] - max_heap[0]) / 2
		if len(min_heap) > len(max_heap):
			return min_heap[0]
		return -max_heap[0]

	def insertHeaps(self, x):
		median = self.getMedian()
		if median is None:
			median = 0
		if x > median:
			heapq.heappush(min_heap, x)
		else:
			heapq.heappush(max_heap, -x)
		self.balanceHeaps()


import heapq

class Solution:

	def __init__(self):
		self.min = []
		self.max = []
		self.n = 0
		self.m = 0

	def balanceHeaps(self):
		if self.n > 0 and self.m > 0:
			if -self.max[0] > self.min[0]:
				k = -heapq.heappop(self.max)
				q = heapq.heappop(self.min)
				heapq.heappush(self.min, k)
				heapq.heappush(self.max, -q)

	def getMedian(self):
		if (self.n + self.m) % 2 == 1:
			return -self.max[0]
		else:
			return (-self.max[0] + self.min[0]) / 2

	def insertHeaps(self, x):
		if self.n <= self.m:
			heapq.heappush(self.max, -x)
			self.n = self.n + 1
		else:
			heapq.heappush(self.min, x)
			self.m = self.m + 1
		self.balanceHeaps()


class Solution:
	minheap = []
	maxheap = []
	len_min = 0
	len_max = 0
	c_median = 0

	def balanceHeaps(self):
		while self.len_min < self.len_max:
			heapq.heappush(self.minheap, -1 * heapq.heappop(self.maxheap))
			self.len_min += 1
			self.len_max -= 1
		if self.len_max >= 1:
			while -1 * self.minheap[0] > self.maxheap[0]:
				heapq.heappush(self.maxheap, -1 * heapq.heappop(self.minheap))
				heapq.heappush(self.minheap, -1 * heapq.heappop(self.maxheap))

	def getMedian(self):
		if self.len_min == self.len_max:
			return (-1 * self.minheap[0] + self.maxheap[0]) / 2
		else:
			return -1 * self.minheap[0]

	def insertHeaps(self, x):
		heapq.heappush(self.maxheap, x)
		self.len_max += 1
		self.balanceHeaps()


from heapq import heappush, heappop, heapify

class Solution:

	def __init__(self):
		self.minh = []
		self.maxh = []

	def balanceHeaps(self):
		if len(self.minh) > len(self.maxh):
			heapq.heappush(self.maxh, -heapq.heappop(self.minh))

	def getMedian(self):
		if len(self.minh) == len(self.maxh):
			f = -self.maxh[0]
			s = self.minh[0]
			return (f + s) / 2.0
		else:
			return -self.maxh[0]

	def insertHeaps(self, x):
		heappush(self.maxh, -x)
		heappush(self.minh, -heappop(self.maxh))
		self.balanceHeaps()


import heapq as hq

class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []

	def getMedian(self):
		if len(self.min_heap) == len(self.max_heap):
			return (self.min_heap[0] - self.max_heap[0]) / 2
		return self.min_heap[0]

	def insertHeaps(self, x):
		if len(self.min_heap) == len(self.max_heap):
			hq.heappush(self.min_heap, -hq.heappushpop(self.max_heap, -x))
		else:
			hq.heappush(self.max_heap, -hq.heappushpop(self.min_heap, x))


from heapq import heapify, heappush, heappop

class Solution:

	def __init__(self):
		(self.small, self.large) = ([], [])
		heapify(self.small)
		heapify(self.large)

	def balanceHeaps(self):
		if self.small and self.large and (-self.small[0] > self.large[0]):
			val = -heappop(self.small)
			heappush(self.large, val)
		if len(self.small) - len(self.large) > 1:
			val = -heappop(self.small)
			heappush(self.large, val)
		if len(self.large) - len(self.small) > 1:
			val = -heappop(self.large)
			heappush(self.small, val)

	def getMedian(self):
		if len(self.small) > len(self.large):
			return -self.small[0]
		if len(self.large) > len(self.small):
			return self.large[0]
		return (-1 * self.small[0] + self.large[0]) / 2

	def insertHeaps(self, x):
		heappush(self.small, -x)
		self.balanceHeaps()


from heapq import heappush, heappop, heapify

class Solution:
	minHeap = []
	maxHeap = []

	def balanceHeaps(self):
		if len(self.maxHeap) > len(self.minHeap) + 1:
			heappush(self.minHeap, -heappop(self.maxHeap))
		elif len(self.maxHeap) < len(self.minHeap):
			heappush(self.maxHeap, -heappop(self.minHeap))

	def getMedian(self):
		if len(self.maxHeap) == len(self.minHeap):
			return (-self.maxHeap[0] + self.minHeap[0]) / 2
		else:
			return -self.maxHeap[0]

	def insertHeaps(self, x):
		if len(self.maxHeap) == 0:
			heappush(self.maxHeap, -x)
		elif -self.maxHeap[0] > x:
			heappush(self.maxHeap, -x)
		else:
			heappush(self.minHeap, x)
		self.balanceHeaps()


from heapq import *

class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []
		self.median = 0

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.max_heap) == len(self.min_heap):
			self.median = (-self.max_heap[0] + self.min_heap[0]) / 2
			return self.median
		elif len(self.max_heap) > len(self.min_heap):
			self.median = -self.max_heap[0]
			return self.median
		else:
			self.median = self.min_heap[0]
			return self.median

	def insertHeaps(self, x):
		if len(self.max_heap) == 0 and len(self.min_heap) == 0:
			heappush(self.min_heap, x)
		elif x < self.min_heap[0]:
			heappush(self.max_heap, -x)
		else:
			heappush(self.min_heap, x)
		while abs(len(self.max_heap) - len(self.min_heap)) > 1:
			if len(self.max_heap) > len(self.min_heap):
				heappush(self.min_heap, -heappop(self.max_heap))
			else:
				heappush(self.max_heap, -heappop(self.min_heap))


class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []

	def balanceHeaps(self):
		if len(self.max_heap) > len(self.min_heap) + 1:
			val = -heapq.heappop(self.max_heap)
			heapq.heappush(self.min_heap, val)
		elif len(self.min_heap) > len(self.max_heap) + 1:
			val = -heapq.heappop(self.min_heap)
			heapq.heappush(self.max_heap, val)

	def getMedian(self):
		if len(self.min_heap) == len(self.max_heap):
			return (self.min_heap[0] - self.max_heap[0]) / 2
		elif len(self.min_heap) > len(self.max_heap):
			return self.min_heap[0]
		else:
			return -self.max_heap[0]

	def insertHeaps(self, x):
		if not self.max_heap or x < -self.max_heap[0]:
			heapq.heappush(self.max_heap, -x)
		else:
			heapq.heappush(self.min_heap, x)
		self.balanceHeaps()


class Solution:
	lHeap = []
	rHeap = []

	def balanceHeaps(self):
		d = len(self.lHeap) - len(self.rHeap)
		if abs(d) > 1:
			if d > 0:
				x = heapq.heappop(self.lHeap) * -1
				heapq.heappush(self.rHeap, x)
			else:
				x = heapq.heappop(self.rHeap)
				heapq.heappush(self.lHeap, x * -1)

	def getMedian(self):
		d = len(self.lHeap) - len(self.rHeap)
		if d == 0:
			lMax = self.lHeap[0] * -1
			rMin = self.rHeap[0]
			return (lMax + rMin) / 2
		elif d > 0:
			return self.lHeap[0] * -1
		else:
			return self.rHeap[0]

	def insertHeaps(self, x):
		if len(self.lHeap) == 0:
			heapq.heappush(self.lHeap, x * -1)
		elif x < self.lHeap[0] * -1:
			heapq.heappush(self.lHeap, x * -1)
		else:
			heapq.heappush(self.rHeap, x)
		self.balanceHeaps()


class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []

	def balanceHeaps(self):
		if len(self.min_heap) > len(self.max_heap):
			heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

	def getMedian(self):
		if len(self.min_heap) != len(self.max_heap):
			return -self.max_heap[0]
		else:
			return (self.min_heap[0] - self.max_heap[0]) / 2

	def insertHeaps(self, x):
		heapq.heappush(self.max_heap, -x)
		heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
		self.balanceHeaps()


from heapq import heappush, heappop

class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []

	def balanceHeaps(self):
		if abs(len(self.min_heap) - len(self.max_heap)) > 1:
			if len(self.min_heap) > len(self.max_heap):
				root = heapq.heappop(self.min_heap)
				heapq.heappush(self.max_heap, -root)
			else:
				root = heapq.heappop(self.max_heap)
				heapq.heappush(self.min_heap, -root)

	def getMedian(self):
		if len(self.min_heap) == len(self.max_heap):
			return (self.min_heap[0] - self.max_heap[0]) / 2.0
		elif len(self.min_heap) > len(self.max_heap):
			return float(self.min_heap[0])
		else:
			return -float(self.max_heap[0])

	def insertHeaps(self, x):
		if not self.max_heap or x < -self.max_heap[0]:
			heapq.heappush(self.max_heap, -x)
		else:
			heapq.heappush(self.min_heap, x)
		self.balanceHeaps()


import heapq as h

class Solution:

	def __init__(self):
		self.m1 = []
		self.m2 = []
		h.heapify(self.m1)
		h.heapify(self.m2)

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.m1) == len(self.m2):
			return (self.m2[0] - self.m1[0]) / 2
		return -self.m1[0]

	def insertHeaps(self, x):
		if len(self.m1) == 0:
			h.heappush(self.m1, -x)
			return
		if len(self.m2) == 0:
			if -self.m1[0] <= x:
				h.heappush(self.m2, x)
			if -self.m1[0] > x:
				y = h.heappop(self.m1)
				y = -y
				h.heappush(self.m2, y)
				h.heappush(self.m1, -x)
			return
		(a, b) = (self.m1[0], self.m2[0])
		if len(self.m1) == len(self.m2):
			if x >= b:
				y = h.heappop(self.m2)
				h.heappush(self.m1, -y)
				h.heappush(self.m2, x)
				return
			h.heappush(self.m1, -x)
			return
		if len(self.m1) > len(self.m2):
			if x >= -a:
				h.heappush(self.m2, x)
				return
			if -a >= x:
				y = h.heappop(self.m1)
				h.heappush(self.m1, -x)
				h.heappush(self.m2, -y)
				return


class Solution:

	def __init__(self):
		self.maxhp = []
		self.minhp = []

	def getMedian(self):
		if len(self.maxhp) > len(self.minhp):
			return -self.maxhp[0]
		elif len(self.minhp) > len(self.maxhp):
			return self.minhp[0]
		return (-self.maxhp[0] + self.minhp[0]) / 2

	def insertHeaps(self, num):
		if not self.maxhp:
			self.maxhp.append(-num)
		elif not self.minhp:
			self.minhp.append(num)
			if -self.maxhp[0] > self.minhp[0]:
				(self.maxhp[0], self.minhp[0]) = (-self.minhp[0], -self.maxhp[0])
		elif num < self.minhp[0]:
			heapq.heappush(self.maxhp, -num)
		else:
			heapq.heappush(self.minhp, num)
		if len(self.maxhp) > len(self.minhp) + 1:
			heapq.heappush(self.minhp, -heapq.heappop(self.maxhp))
		elif len(self.minhp) > len(self.maxhp) + 1:
			heapq.heappush(self.maxhp, -heapq.heappop(self.minhp))


import heapq

class Solution:

	def __init__(self):
		self.max_heap = []
		self.min_heap = []

	def insertHeaps(self, x: int) -> None:
		if not self.max_heap or x < -self.max_heap[0]:
			heapq.heappush(self.max_heap, -x)
		else:
			heapq.heappush(self.min_heap, x)
		self.balanceHeaps()

	def balanceHeaps(self) -> None:
		if len(self.max_heap) - len(self.min_heap) > 1:
			heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
		elif len(self.min_heap) - len(self.max_heap) > 1:
			heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

	def getMedian(self) -> float:
		if len(self.max_heap) == len(self.min_heap):
			return (-self.max_heap[0] + self.min_heap[0]) / 2
		elif len(self.max_heap) > len(self.min_heap):
			return -self.max_heap[0]
		else:
			return self.min_heap[0]


class Solution:

	def __init__(self):
		self.minh = []
		self.maxh = []

	def balanceHeaps(self):
		if abs(len(self.minh) - len(self.maxh)) > 1:
			heapq.heappush(self.minh, -heapq.heappop(self.maxh))
		if self.minh and -self.maxh[0] > self.minh[0]:
			heapq.heappush(self.minh, -heapq.heappop(self.maxh))
			heapq.heappush(self.maxh, -heapq.heappop(self.minh))

	def getMedian(self):
		if (len(self.maxh) + len(self.minh)) % 2 != 0:
			return -self.maxh[0]
		else:
			return (-self.maxh[0] + self.minh[0]) / 2

	def insertHeaps(self, x):
		heapq.heappush(self.maxh, -x)
		self.balanceHeaps()


class Solution:

	def __init__(self):
		self.heap1 = []
		self.heap2 = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.heap1) == len(self.heap2):
			return (self.heap2[0] - self.heap1[0]) / 2.0
		else:
			return -self.heap1[0]

	def insertHeaps(self, x):
		if len(self.heap1) == 0:
			heapq.heappush(self.heap1, -x)
			return
		if len(self.heap1) > len(self.heap2):
			if x > -self.heap1[0]:
				heapq.heappush(self.heap2, x)
			else:
				heapq.heappush(self.heap2, -heapq.heappop(self.heap1))
				heapq.heappush(self.heap1, -x)
		elif len(self.heap1) == len(self.heap2):
			if x > -self.heap1[0] and x < self.heap2[0]:
				heapq.heappush(self.heap1, -x)
			elif x > self.heap2[0]:
				heapq.heappush(self.heap1, -heapq.heappop(self.heap2))
				heapq.heappush(self.heap2, x)
			else:
				heapq.heappush(self.heap1, -x)


class Solution:

	def __init__(self):
		self.low = []
		self.high = []

	def balanceHeaps(self):
		if self.low:
			heapq.heappush(self.high, -heapq.heappop(self.low))
		while len(self.high) > len(self.low):
			heapq.heappush(self.low, -heapq.heappop(self.high))

	def getMedian(self):
		if len(self.low) == len(self.high):
			return (-self.low[0] + self.high[0]) / 2.0
		else:
			return -self.low[0]

	def insertHeaps(self, x):
		heapq.heappush(self.high, x)
		self.balanceHeaps()


class Solution:
	minHeap = []
	maxHeap = []

	def __init__(self):
		minHeap = []
		heapq.heapify(minHeap)
		maxHeap = []
		heapq.heapify(maxHeap)

	def getMedian(self):
		if len(self.minHeap) != len(self.maxHeap):
			return -self.maxHeap[0]
		else:
			return (self.minHeap[0] - self.maxHeap[0]) / 2

	def insertHeaps(self, num):
		heapq.heappush(self.maxHeap, -num)
		heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
		if len(self.minHeap) > len(self.maxHeap):
			heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))


import heapq

class Solution:
	(left, right) = ([], [])
	heapq.heapify(left)
	heapq.heapify(right)

	def balanceHeaps(self):
		while len(self.left) - len(self.right) > 1:
			heapq.heappush(self.right, -heapq.heappop(self.left))
		while len(self.right) - len(self.left) >= 1:
			heapq.heappush(self.left, -heapq.heappop(self.right))

	def getMedian(self):
		if len(self.left) == len(self.right):
			return (-self.left[0] + self.right[0]) / 2
		else:
			return -self.left[0]

	def insertHeaps(self, x):
		if len(self.left) == 0 or x <= -self.left[0]:
			heapq.heappush(self.left, -x)
		else:
			heapq.heappush(self.right, x)
		self.balanceHeaps()


from queue import PriorityQueue

class Solution:

	def __init__(self):
		self.lower = PriorityQueue()
		self.higher = PriorityQueue()
		(self.lcnt, self.hcnt) = (0, 0)

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if self.lcnt == self.hcnt:
			(a, b) = (-1 * self.lower.get(), self.higher.get())
			self.lower.put(-1 * a)
			self.higher.put(b)
			return (a + b) / 2
		elif self.lcnt > self.hcnt:
			a = -1 * self.lower.get()
			self.lower.put(-1 * a)
			return a
		else:
			a = self.higher.get()
			self.higher.put(a)
			return a

	def insertHeaps(self, x):
		if self.hcnt == 0:
			self.higher.put(x)
			self.hcnt += 1
			return
		y = self.higher.get()
		self.higher.put(y)
		if x < y:
			self.lower.put(-1 * x)
			self.lcnt += 1
		else:
			self.higher.put(x)
			self.hcnt += 1
		if self.lcnt - self.hcnt > 1:
			self.higher.put(-1 * self.lower.get())
			self.hcnt += 1
			self.lcnt -= 1
		elif self.hcnt - self.lcnt > 1:
			self.lower.put(-1 * self.higher.get())
			self.lcnt += 1
			self.hcnt -= 1


from heapq import heappush, heappop

class Solution:

	def __init__(self):
		self.maxHeap = []
		self.minHeap = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		n = len(self.minHeap) + len(self.maxHeap)
		if n & 1:
			return -self.maxHeap[0]
		return (self.minHeap[0] + -self.maxHeap[0]) / 2

	def insertHeaps(self, x):
		if not self.maxHeap or x <= -self.maxHeap[0]:
			heappush(self.maxHeap, -x)
			if len(self.maxHeap) == len(self.minHeap) + 2:
				popped = -heappop(self.maxHeap)
				heappush(self.minHeap, popped)
		else:
			heappush(self.minHeap, x)
			if len(self.minHeap) > len(self.maxHeap):
				popped = heappop(self.minHeap)
				heappush(self.maxHeap, -popped)


import heapq

class Solution:

	def __init__(self):
		self.minheap = []
		self.maxheap = []

	def getMedian(self):
		m = len(self.maxheap)
		n = len(self.minheap)
		if m == n:
			a = -self.maxheap[0]
			b = self.minheap[0]
			return (a + b) / 2
		else:
			return -self.maxheap[0]

	def insertHeaps(self, x):
		m = len(self.maxheap)
		n = len(self.minheap)
		if m == 0 and n == 0:
			heapq.heappush(self.maxheap, -x)
		elif m > n:
			if -self.maxheap[0] < x:
				heapq.heappush(self.minheap, x)
			else:
				a = -heapq.heappop(self.maxheap)
				heapq.heappush(self.minheap, a)
				heapq.heappush(self.maxheap, -x)
		elif self.minheap[0] > x:
			heapq.heappush(self.maxheap, -x)
		else:
			a = heapq.heappop(self.minheap)
			heapq.heappush(self.maxheap, -a)
			heapq.heappush(self.minheap, x)


from heapq import heapify, heappush, heappop

class Solution:
	ele = []
	ans = []
	size = -1
	minHeap = []
	maxHeap = []
	curMedian = 0

	def balanceHeaps(self):
		mini = len(self.minHeap)
		maxi = len(self.maxHeap)
		if mini == maxi:
			return 0
		elif maxi > mini:
			return 1
		else:
			return -1

	def callMedian(self, x):
		flag = self.balanceHeaps()
		if flag == 0:
			if x > self.curMedian:
				heapq.heappush(self.minHeap, x)
				self.curMedian = self.minHeap[0]
			else:
				heapq.heappush(self.maxHeap, -x)
				self.curMedian = -self.maxHeap[0]
		elif flag == 1:
			if x > self.curMedian:
				heapq.heappush(self.minHeap, x)
			else:
				heapq.heappush(self.minHeap, -self.maxHeap[0])
				heapq.heappop(self.maxHeap)
				heapq.heappush(self.maxHeap, -x)
			self.curMedian = (self.minHeap[0] + -self.maxHeap[0]) / 2
		else:
			if x > self.curMedian:
				heapq.heappush(self.maxHeap, -self.minHeap[0])
				heapq.heappop(self.minHeap)
				heapq.heappush(self.minHeap, x)
			else:
				heapq.heappush(self.maxHeap, -x)
			self.curMedian = (self.minHeap[0] + -self.maxHeap[0]) / 2

	def getMedian(self):
		self.callMedian(self.ele[self.size])
		return self.curMedian

	def insertHeaps(self, x):
		self.ele.append(x)
		self.size += 1
		self.getMedian()


from heapq import heappush, heappop, heapify

class Solution:

	def __init__(self):
		self.minHeap = []
		self.minHeapSize = 0
		self.maxHeap = []
		self.maxHeapSize = 0

	def balanceHeaps(self):
		if self.maxHeapSize > self.minHeapSize:
			heappush(self.minHeap, -heappop(self.maxHeap))
			self.minHeapSize += 1
			self.maxHeapSize -= 1
		else:
			heappush(self.maxHeap, -heappop(self.minHeap))
			self.minHeapSize -= 1
			self.maxHeapSize += 1

	def getMedian(self):
		if self.minHeapSize == self.maxHeapSize:
			return (self.minHeap[0] + -self.maxHeap[0]) / 2
		elif self.minHeapSize < self.maxHeapSize:
			return -self.maxHeap[0]
		else:
			return self.minHeap[0]

	def insertHeaps(self, x):
		if not self.maxHeap or x <= -self.maxHeap[0]:
			heappush(self.maxHeap, -x)
			self.maxHeapSize += 1
		else:
			heappush(self.minHeap, x)
			self.minHeapSize += 1
		if abs(self.maxHeapSize - self.minHeapSize) > 1:
			self.balanceHeaps()


class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []
		heapq.heapify(self.min_heap)
		heapq.heapify(self.max_heap)

	def balanceHeaps(self):

	def getMedian(self):
		if len(self.max_heap) == len(self.min_heap):
			median = (self.max_heap[0] - self.min_heap[0]) / 2
		elif len(self.max_heap) > len(self.min_heap):
			median = self.max_heap[0]
		else:
			median = self.min_heap[0]
		return median

	def insertHeaps(self, x):
		heapq.heappush(self.max_heap, x)
		val = heapq.heappop(self.max_heap)
		heapq.heappush(self.min_heap, -val)
		if len(self.min_heap) > len(self.max_heap):
			val = heapq.heappop(self.min_heap)
			heapq.heappush(self.max_heap, -val)


import heapq

class Solution:

	def __init__(self):
		self.minHeap = []
		self.maxHeap = []

	def balanceHeaps(self):
		pass

	def getMedian(self):
		if len(self.minHeap) > len(self.maxHeap):
			return self.minHeap[0]
		else:
			return (self.minHeap[0] - self.maxHeap[0]) / 2

	def insertHeaps(self, x):
		if len(self.minHeap) == len(self.maxHeap):
			heapq.heappush(self.maxHeap, -x)
			heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
		else:
			heapq.heappush(self.minHeap, x)
			heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))


class Solution:

	def __init__(self):
		self.s = []
		self.g = []

	def insertHeaps(self, x):
		if len(self.s) == 0:
			heapq.heappush(self.s, -x)
			return
		if len(self.s) > len(self.g):
			if x < -self.s[0]:
				heapq.heappush(self.g, -heapq.heappop(self.s))
				heapq.heappush(self.s, -x)
			else:
				heapq.heappush(self.g, x)
		elif x < -self.s[0]:
			heapq.heappush(self.s, -x)
		else:
			heapq.heappush(self.g, x)
			heapq.heappush(self.s, -heapq.heappop(self.g))

	def getMedian(self):
		if len(self.s) == len(self.g):
			return float(-self.s[0] + self.g[0]) / 2
		else:
			return -float(self.s[0])


import heapq

class Solution:

	def __init__(self):
		self.maxheap = []
		self.minheap = []
		heapq.heapify(self.maxheap)
		heapq.heapify(self.minheap)

	def balanceHeaps(self):
		if len(self.minheap) > len(self.maxheap):
			heapq.heappush(self.maxheap, -heapq.heappop(self.minheap))
		return None

	def getMedian(self):
		if len(self.maxheap) == len(self.minheap):
			return (-self.maxheap[0] + self.minheap[0]) / 2
		else:
			return -self.maxheap[0]

	def insertHeaps(self, x):
		heapq.heappush(self.maxheap, -x)
		heapq.heappush(self.minheap, -heapq.heappop(self.maxheap))
		self.balanceHeaps()
		return None


class Solution:

	def __init__(self):
		self.max_heap = []
		self.min_heap = []
		self.total = 0
		heapq.heapify(self.max_heap)
		heapq.heapify(self.min_heap)

	def balanceHeaps(self):
		lenmh = len(self.max_heap)
		lenlh = len(self.min_heap)
		if lenmh >= lenlh + 2:
			heapq.heappush(self.min_heap, -1 * heapq.heappop(self.max_heap))
		if lenlh > lenmh:
			heapq.heappush(self.max_heap, -1 * heapq.heappop(self.min_heap))

	def getMedian(self):
		if not self.total:
			return
		if self.total % 2 != 0:
			return -1 * self.max_heap[0]
		else:
			return (-1 * self.max_heap[0] + self.min_heap[0]) / 2

	def insertHeaps(self, x):
		self.total += 1
		if not self.max_heap:
			heapq.heappush(self.max_heap, -1 * x)
			return
		if x > -1 * self.max_heap[0]:
			heapq.heappush(self.min_heap, x)
		else:
			heapq.heappush(self.max_heap, -1 * x)
		self.balanceHeaps()


from heapq import heappush, heappop
(min_heap, max_heap) = ([], [])

class Solution:

	def balanceHeaps(self):
		global max_heap
		global min_heap
		if len(min_heap) > len(max_heap):
			heappush(max_heap, -heappop(min_heap))
		elif len(max_heap) > len(min_heap) + 1:
			heappush(min_heap, -heappop(max_heap))

	def getMedian(self):
		global max_heap
		global min_heap
		if not len(min_heap) + len(max_heap) & 1:
			return (-max_heap[0] + min_heap[0]) / 2.0
		return -max_heap[0]

	def insertHeaps(self, x):
		global max_heap
		global min_heap
		if not max_heap or x < -max_heap[0]:
			heappush(max_heap, -x)
		else:
			heappush(min_heap, x)
		self.balanceHeaps()


class Solution:

	def __init__(self):
		self.minHeap = []
		self.maxHeap = []

	def balanceHeaps(self):
		l1 = len(self.minHeap)
		l2 = len(self.maxHeap)
		if l1 == l2 + 2:
			curr = -heapq.heappop(self.minHeap)
			heapq.heappush(self.maxHeap, curr)
		if l2 == l1 + 2:
			curr = -heapq.heappop(self.maxHeap)
			heapq.heappush(self.minHeap, curr)

	def getMedian(self):
		l1 = len(self.minHeap)
		l2 = len(self.maxHeap)
		if l1 == l2:
			return (self.minHeap[0] - self.maxHeap[0]) / 2
		if l1 > l2:
			return self.minHeap[0]
		return -self.maxHeap[0]

	def insertHeaps(self, x):
		if len(self.maxHeap) == 0 or x > -self.maxHeap[0]:
			heapq.heappush(self.minHeap, x)
		else:
			heapq.heappush(self.maxHeap, -x)
		self.balanceHeaps()


class Solution:
	minheap = []
	maxheap = []

	def balanceHeaps(self):
		l1 = len(self.maxheap)
		l2 = len(self.minheap)
		if l1 - l2 == -1:
			heapq.heappush(self.maxheap, -1 * heapq.heappop(self.minheap))
		else:
			heapq.heappush(self.minheap, -1 * heapq.heappop(self.maxheap))

	def getMedian(self):
		l1 = len(self.maxheap)
		l2 = len(self.minheap)
		if l1 == l2:
			return (self.minheap[0] + -1 * self.maxheap[0]) / 2
		elif l1 - l2 == -1:
			return self.minheap[0]
		else:
			return -1 * self.maxheap[0]

	def insertHeaps(self, x):
		l1 = len(self.maxheap)
		l2 = len(self.minheap)
		median = 0
		if l1 == l2:
			if l1:
				median = (self.minheap[0] + -1 * self.maxheap[0]) / 2
			if x > median:
				heapq.heappush(self.minheap, x)
			else:
				heapq.heappush(self.maxheap, -x)
		elif l1 - l2 == -1:
			median = self.minheap[0]
			if x < median:
				heapq.heappush(self.maxheap, -x)
			else:
				self.balanceHeaps()
				heapq.heappush(self.minheap, x)
		else:
			median = -1 * self.maxheap[0]
			if x > median:
				heapq.heappush(self.minheap, x)
			else:
				self.balanceHeaps()
				heapq.heappush(self.maxheap, -x)


class Solution:

	def __init__(self):
		self.minHeap = []
		self.maxHeap = []

	def getMedian(self):
		if len(self.minHeap) == len(self.maxHeap):
			return (self.minHeap[0] - self.maxHeap[0]) / 2
		return -self.maxHeap[0]

	def insertHeaps(self, x):
		heapq.heappush(self.maxHeap, -x)
		heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))
		if len(self.minHeap) > len(self.maxHeap):
			heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))


class Solution:

	def __init__(self):
		self.min_heap = []
		self.max_heap = []

	def balanceHeaps(self):
		if len(self.max_heap) - len(self.min_heap) == 2:
			heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
		elif len(self.max_heap) - len(self.min_heap) == 1:
			heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
			heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

	def getMedian(self):
		if len(self.max_heap) - len(self.min_heap) == 1:
			return -self.max_heap[0]
		res = (-self.max_heap[0] + self.min_heap[0]) / 2
		return res

	def insertHeaps(self, x):
		heapq.heappush(self.max_heap, -x)
		self.balanceHeaps()


from heapq import heapify, heappush, heappop

class Solution:

	def __init__(self):
		self.maxHeap = []
		self.minHeap = []

	def getMedian(self):
		m = len(self.maxHeap)
		n = len(self.minHeap)
		if m == n:
			a = -self.maxHeap[0]
			b = self.minHeap[0]
			return (a + b) / 2
		else:
			return -self.maxHeap[0]

	def insertHeaps(self, x):
		m = len(self.maxHeap)
		n = len(self.minHeap)
		if m == 0 and n == 0:
			heappush(self.maxHeap, -x)
		elif m > n:
			if -self.maxHeap[0] > x:
				a = -heappop(self.maxHeap)
				heappush(self.minHeap, a)
				heappush(self.maxHeap, -x)
			else:
				heappush(self.minHeap, x)
		elif self.minHeap[0] < x:
			a = heappop(self.minHeap)
			heappush(self.maxHeap, -a)
			heappush(self.minHeap, x)
		else:
			heappush(self.maxHeap, -x)