We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I loved this approach. Here is the same solution, with a different class structure.
importheapqclassMinHeap:""" Maintain a max-heap for the lower half of values and a min-heap for higher half of values """def__init__(self):self.heap=[]defpeek(self):returnself.heap[0]ifself.heapelsefloat('+inf')defpush(self,data):heapq.heappush(self.heap,data)defreplace(self,data):returnheapq.heapreplace(self.heap,data)defsize(self):returnlen(self.heap)classMaxHeap(MinHeap):""" Pythons heapq methods are for a min-heap, so data are inverted in the max heap """defpeek(self):return-self.heap[0]ifself.heapelsefloat('-inf')defpush(self,data):heapq.heappush(self.heap,-data)defreplace(self,data):return-heapq.heapreplace(self.heap,-data)classRunningMedian:def__init__(self):self._minheap=MinHeap()self._maxheap=MaxHeap()def__str__(self):return"\n".join([" ".join(map(str,map(lambdad:-d,self._maxheap.heap)))," ".join(map(str,self._minheap.heap))])defadd(self,data):ifself._maxheap.size()==self._minheap.size():ifdata<self._minheap.peek()ornotlen(self._minheap.heap):self._maxheap.push(data)else:self._maxheap.push(self._minheap.replace(data))else:ifdata>self._maxheap.peek()ornotlen(self._maxheap.heap):self._minheap.push(data)else:self._minheap.push(self._maxheap.replace(data))defmedian(self):ifself._maxheap.size()==self._minheap.size():return(self._maxheap.peek()+self._minheap.peek())/2else:returnself._maxheap.peek()rm=RunningMedian()for_inrange(int(input())):a=int(input())rm.add(a)print("{:.1f}".format(rm.median()))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Heaps: Find the Running Median
You are viewing a single comment's thread. Return to all comments →
I loved this approach. Here is the same solution, with a different class structure.