title: return kth greatest element [ better than O(n) ]
body: <p>I have a stream (whose length I do not know, theoretically may be infinity).</p>
  
  <p>I read the stream's elements one by one.</p>
  
  <p>Every time an element is read from the stream, I want to be able to return the <code>k</code>th greatest element read so far.</p>
  
  <p>(Ideally for me it would be a code in python and/or lisp/scheme).</p>
  
  <p>K is read at the beginning, and K can be a NUMBER (3rd, 4th), or can be a PROCENT (K % of the total nr. of elements read so far). If K=1/2, that means to extract the median element each time... For example, after reading Nth element, it must return N/2 th greatest element</p>
  
  <p>example K=1/2:</p>
  
  <pre><code>3 -&gt; 3
  3,4 -&gt; 3
  3,4,2 -&gt; 3
  3,4,2,1 -&gt; 2
  etc.
  </code></pre>
  
  <p>I think this example is enough to clarify the question. I need minimal possible time to extract the Kth element. (this supposes read the stream in O(1), then insert the read value , then extract the Kth element).</p>
  
  <p>I want any solution better than O(n).</p>