I did treaps, too: <a href="http://programmingpraxis.com/2009/06/26/treaps/">http://programmingpraxis.com/2009/06/26/treaps/</a>.  And I use them all the time, including where most people probably use hash tables, because so often you need the keys in order somewhere in your program.<br>
<br><div class="gmail_quote">On Thu, Sep 9, 2010 at 11:03 AM, Prabhakar Ragde <span dir="ltr">&lt;<a href="mailto:plragde@uwaterloo.ca">plragde@uwaterloo.ca</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On 9/9/10 11:33 AM, Phil Bewig wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<a href="http://programmingpraxis.com/2009/12/11/selection/" target="_blank">http://programmingpraxis.com/2009/12/11/selection/</a><br>
</blockquote>
<br></div>
This method takes O(n) time with high probability if the partitioning element is chosen deterministically and the data is randomly permuted (with all permutations equally likely) or if the partitioning element is chosen uniformly at random. Its deterministic worst-case cost is O(n^2). However, for a site called &quot;Programming Praxis&quot;, it&#39;s definitely the right choice.<br>

<br>
Our attitude towards randomness in computer science is a bit strange. I&#39;m convinced most of our students graduate thinking that Quicksort is an O(n log n) algorithm, but this is only true in a probabilistic model. On the other hand, the shortest, cleanest, and most elegant method I know of to balance binary search trees (which underlies non-hash efficient set and map implementations) uses randomness, but no one talks about it or knows it. --PR<br>

</blockquote></div><br>