[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: "Inside quick sort, there is a binary tree waiting to be discovered"**
**From**: Rici Lake <lua@...>
**Date**: Thu, 1 Dec 2005 19:24:10 -0500

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.
`