On Tue, Mar 20, 2012 at 6:31 AM, Tom Lane <t...@sss.pgh.pa.us> wrote: > Greg Stark <st...@mit.edu> writes: >> Offhand I wonder if this is all because we don't have the O(n) heapify >> implemented.
I think we do already have it implemented. 1/2 the time the tuple stays where it is after one comparison, 1/4 it moves up one level with two comparisons, 1/8 it moves up two levels with 3 comparisons, etc. That series sums up to a constant. Maybe there is a worst-case that makes this fall apart, though. Heapifying something which is already reverse sorted, maybe? > Robert muttered something about that before, but is it real? If you > could do that, I'd think you'd have a less-than-n-log-n sorting > solution. Turning random tuples into heap can be linear. Extracting them while maintaining the heap is NlogN, though. You can't sort without the extraction step, so the law is preserved. Cheers, Jeff -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
