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

Sort by

recency

|

188 Discussions

|

  • roilylitter
     + 0 comments

    Done it with the AVL Tree. Every node of the tree tracks not only height but also size which allows to calculate the index of the node and therefore the median.

    def print_median(tree):
    if not tree:
        print("Wrong!")
        return

    if tree.root.size % 2:
        m = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        if m is None:
            print("Wrong!")
        else:
            print(m.value)
    else:
        m1 = tree[(tree.root.size // 2) + (tree.root.size % 2)]
        m2 = tree[(tree.root.size // 2) + (tree.root.size % 2) + 1]

        if not m1 and not m2:
            print("Wrong!")
        else:
            print(round((m1.value + m2.value) / 2, 1) if (m1.value + m2.value) % 2 else (m1.value + m2.value) // 2)


def median(a, x):
    tree = AVL()

    for e in zip(a, x):
        if e[0] == 'a':
            tree.insert_value(e[1])
            print_median(tree)
        elif e[0] == 'r':
            m = tree.search_value(e[1])
            if m is None:
                print("Wrong!")
            else:
                tree.delete_value(e[1])
                print_median(tree)

    ` class AVL: def init(self): self.root = None

    def __len__(self):
    return self.len(self.root)

def __getitem__(self, idx):

    if idx == 0:
        return self.min_node(self.root)

    if not self.root or idx > self.root.size or idx < 0:
        raise IndexError()

    tmp = self.root
    elms = 0
    while tmp and not (idx == (elms + self.len(tmp.left) + 1)):
        if idx < (elms + self.len(tmp.left) + 1):
            tmp = tmp.left
        elif idx > (elms + self.len(tmp.left) + 1):
            elms += (self.len(tmp.left) + 1)
            tmp = tmp.right
    else:
        return tmp

    The rest of the AVL tree implementation you may find on geeksforgeeks.

  • ayman_gamal
     + 0 comments

    i got this one

    https://ideone.com/YWjB9B

  • Charan_Donthi
     + 0 comments

    Simple solution

    import bisect
def median(a,x):
    ll=[]
    
    
    for (l,r) in zip(a,x):
        if l=='r':
            if r in ll:
                index=bisect.bisect(ll,r)
                ll.pop(index-1)
            else:
                print("Wrong!")
                continue
                
        else:
            bisect.insort(ll,r)
        if(len(ll)==0):
            print("Wrong!")
            continue
        median=(ll[len(ll)//2]+ll[(len(ll)-1)//2])/2
        x=str(median)
        x=x.rstrip('0')
        x=x.rstrip('.')
        print(x)

  • 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)

  • dehaka
     + 0 comments
    void balance(multiset<long>& lower, multiset<long>& upper) {
    if (lower.size() > upper.size() + 1) {
        upper.insert(*lower.rbegin());
        auto rit = lower.rbegin();
        auto it = rit.base();
        lower.erase(--it);
    }
    else if (lower.size() + 1 < upper.size()) {
        lower.insert(*upper.begin());
        upper.erase(upper.begin());
    }
}


void median(vector<char> s, vector<int> X) {
    multiset<long> lower = { -3000000000 };
    multiset<long> upper = { 3000000000 };
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'a') {
            if (X[i] <= *lower.rbegin()) {
                lower.insert(X[i]);
            }
            else {
                upper.insert(X[i]);
            }
        }
        if (s[i] == 'r') {
            if (X[i] <= *lower.rbegin()) {
                auto it = lower.find(X[i]);
                if (it != lower.end()) {
                    lower.erase(it);
                }
                else {
                    cout << "Wrong!" << "\n";
                    continue;
                }
            }
            else if (X[i] >= *upper.begin()) {
                auto it = upper.find(X[i]);
                if (it != upper.end()) {
                    upper.erase(it);
                }
                else {
                    cout << "Wrong!" << "\n";
                    continue;
                }
            }
            else {
                cout << "Wrong!" << "\n";
                continue;
            }
        }
        balance(lower, upper);
        if (lower.size() == upper.size() + 1) {
            cout << *lower.rbegin() << "\n";
        }
        else if (lower.size() + 1 == upper.size()) {
            cout << *upper.begin() << "\n";
        }
        else if (lower.size() == upper.size() and lower.size() != 1) {
            long long a = *lower.rbegin();
            long long b = *upper.begin();
            if ((a + b) % 2 == 0) {
                cout << std::fixed << std::setprecision(0) << (a + b) / 2.0 << "\n";
            }
            else {
                cout << std::fixed << std::setprecision(1) << (a + b) / 2.0 << "\n";
            }
        }
        else {
            cout << "Wrong!" << "\n";
        }
    }
}