Re: "Inside quick sort, there is a binary tree waiting to be discovered"

[Rici Lake <lua@...>]

On 1-Dec-05, at 7:11 PM, Jens Alfke wrote:

> Interesting. This really reminds me of the priority queue, a data 
> structure that lets you push in values and very efficiently pop out 
> the "highest priority" (i.e. largest/smallest) value. It's often used 
> in thread schedulers (to pick the highest-priority ready thread) and 
> simulation engines (to process the chronologically next event.)
>
> A priority queue is usually implemented as a heap, which is a 
> partially-ordered complete binary tree*. The lowest value is always at 
> the top of the tree, and it's very efficient (like O(log n)) to remove 
> it, and to add new values to the tree. I think it's essentially the 
> same sort of lazy sort that you're describing.

Not really, although it certainly has points in common. (For a priority 
queue / heap implementation in Lua, see the code samples at 
<http://lua-users.org/wiki/RiciLake>)

Both quicksort and heapsort have an implicit binary tree in their 
implementation. The difference is that quicksort builds its binary tree 
top-down and heapsort builds the binary tree bottom-up. The practical 
consequence is that lazy heapsort lets you lazily sort the initial 
segment of the result vector (although the usual implementation does 
this destructively) whereas my lazy quicksort lets you lazily sort at 
any point in the vector. In other words, you could not produce an 
efficient solution to the income disparity problem by using a lazy 
heapsort, as far as I can see; you'd need to sort almost the entire 
vector to do so.