Mediaani

Toteuta luokka Median, jossa on seuraavat metodit:

• add(x): lisää luku x
• median(): ilmoita listan mediaani eli keskimmäinen luku suuruusjärjestyksessä (jos lukuja on parillinen määrä, pienempi kahdesta mediaanista)

Kummankin metodin tulee toimia tehokkaasti (ajassa O(1) tai O(\log n)).

Toteuta tiedostoon median.py luokka Median seuraavan mallin mukaisesti.

class Median:
    def __init__(self):
        # TODO

    def add(self, x):
        # TODO

    def median(self):
        # TODO

if __name__ == "__main__":
    m = Median()
    m.add(1)
    print(m.median()) # 1
    m.add(2)
    print(m.median()) # 1
    m.add(1)
    print(m.median()) # 1
    m.add(3)
    print(m.median()) # 1
    m.add(3)
    print(m.median()) # 2

Selitys: Esimerkissä listat ovat [1], [1,2], [1,2,1], [1,2,1,3], [1,2,1,3,3] ja niiden mediaanit ovat 1, 1, 1, 1 ja 2.