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.
  1. Prepare
  2. Data Structures
  3. Balanced Trees
  4. Median Updates
  5. Discussions

Median Updates

  • skoushan
     + 0 comments

    The multi-set solution is O(n) for add and O(n) for remove (thus no better than using a sorted linkedlist). This is a heap based solution that's O(log n) for add but still O(n) for remove.

    from heapq import heappop, heappush, heapify

class MedianTracker:
    def __init__(self):
        self.left = []
        self.right = []

    def _shift_left(self):
        while len(self.right) > len(self.left) + 1:
            num = heappop(self.right)
            heappush(self.left, -num)

    def _shift_right(self):
        while len(self.left) > len(self.right) + 1:
            num = -heappop(self.left)
            heappush(self.right, num)

    def remove(self, num):
        if self.left and num <= -self.left[0]:
            self.left.remove(-num)
            heapify(self.left)
            self._shift_left()
        elif self.right and num >= self.right[0]:
            self.right.remove(num)
            heapify(self.right)
            self._shift_right()
        else:
            raise ValueError('removing element not in list')

    def add(self, num):
        if self.left and num > -self.left[0]:
            heappush(self.right, num)
            self._shift_left()
        else:
            heappush(self.left, -num)
            self._shift_right()

    def _median(self):
        if not self.left and not self.right:
            raise ValueError('no median when empty')
        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 median(self):
        med = self._median()
        if isinstance(med, float) and med.is_integer():
            return int(med)
        return med

#!/bin/python
def median(a,x):
    median_tracker = MedianTracker()
    for op, num in zip(a, x):
        if op == 'r':
            try:
                median_tracker.remove(num)
                print(median_tracker.median())
            except:
                print('Wrong!')
        elif op == 'a':
            median_tracker.add(num)
            print(median_tracker.median())

N = int(input())
s = []
x = []
for i in range(0, N):
   tmp = input().strip().split(' ')
   a, b = [xx for xx in tmp]
   s.append(a)
   x.append(int(b))
median(s,x)