title: Fast algorithm for repeated calculation of percentile?
body: <p>In an algorithm I have to calculate the <a href="http://en.wikipedia.org/wiki/Percentile" rel="noreferrer">75th percentile</a> of a data set whenever I add a value. Right now I am doing this:</p>
  
  <ol>
  <li>Get value <code>x</code></li>
  <li>Insert <code>x</code> in an already sorted array at the back</li>
  <li>swap <code>x</code> down until the array is sorted</li>
  <li>Read the element at position <code>array[array.size * 3/4]</code></li>
  </ol>
  
  <p>Point 3 is O(n), and the rest is O(1), but this is still quite slow, especially if the array gets larger. Is there any way to optimize this?</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>Thanks Nikita! Since I am using C++ this is the solution easiest to implement. Here is the code:</p>
  
  <pre><code>template&lt;class T&gt;
  class IterativePercentile {
  public:
    /// Percentile has to be in range [0, 1(
    IterativePercentile(double percentile)
      : _percentile(percentile)
    { }
  
    // Adds a number in O(log(n))
    void add(const T&amp; x) {
      if (_lower.empty() || x &lt;= _lower.front()) {
        _lower.push_back(x);
        std::push_heap(_lower.begin(), _lower.end(), std::less&lt;T&gt;());
      } else {
        _upper.push_back(x);
        std::push_heap(_upper.begin(), _upper.end(), std::greater&lt;T&gt;());
      }
  
      unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
      if (_lower.size() &gt; size_lower) {
        // lower to upper
        std::pop_heap(_lower.begin(), _lower.end(), std::less&lt;T&gt;());
        _upper.push_back(_lower.back());
        std::push_heap(_upper.begin(), _upper.end(), std::greater&lt;T&gt;());
        _lower.pop_back();
      } else if (_lower.size() &lt; size_lower) {
        // upper to lower
        std::pop_heap(_upper.begin(), _upper.end(), std::greater&lt;T&gt;());
        _lower.push_back(_upper.back());
        std::push_heap(_lower.begin(), _lower.end(), std::less&lt;T&gt;());
        _upper.pop_back();
      }            
    }
  
    /// Access the percentile in O(1)
    const T&amp; get() const {
      return _lower.front();
    }
  
    void clear() {
      _lower.clear();
      _upper.clear();
    }
  
  private:
    double _percentile;
    std::vector&lt;T&gt; _lower;
    std::vector&lt;T&gt; _upper;
  };
  </code></pre>