For people confused about how it updates median properly when k is odd like I was: We have to make sure the median is correct after an insertion and a removal.
To maintain median when inserting with odd number of elements in set:
if new >= med: med++
To maintain median when removing with even number of elements in set:
if old > med: med--;
Now just do an extra med-- when inserting and an extra med++ when removing and you get the original code.