title: C++ Efficiently Calculating a Running Median
body: <p>Those of you that have read my previous questions know about my work at understanding and implementing quicksort and quickselect, as well as some other basic algorithms.</p>
  
  <p>Quickselect is used to calculate the kth smallest element in an unsorted list, and this concept can also be used to find the median in an unsorted list.</p>
  
  <p>This time, I need aid in devising  an efficient technique to calculate the <strong>running median</strong>, because quickselect isn't a good choice as it needs to re-calculate every time the list changes. Because quickselect has to restart everytime, it can't take advantage of previous calculations done, so I'm looking for a different algorithm that's similar (possibly) but is more efficient in the area of running medians.</p>