On 28 Nov '05, at 12:30 PM, Rici Lake 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.
* 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].