On Tue, Mar 20, 2012 at 6:31 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Greg Stark <stark@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