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++

else: no-op

To maintain median when removing with even number of elements in set:

if old > med: med--;

else: no-op

Now just do an extra med-- when inserting and an extra med++ when removing and you get the original code.