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

[Jens Alfke <jens@...>]

On 28 Nov '05, at 12:30 PM, Rici Lake wrote:

Possibly useful, possibly didactic. Details at http://lua-users.org/wiki/LazySort

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.

See: <http://www.brpreiss.com/books/opus4/html/page352.html>

--Jens

* and the tree is usually implemented as a linear array, where the children of a[i] are a[2*i] and a[2*i+1].