On Tue, Mar 20, 2012 at 12:12 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Greg Stark <stark@mit.edu> writes:
>> http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
>
> Interesting. I'm pretty sure that idea appears nowhere in Knuth
> (which might mean it's new enough to have a live patent on it ...
> anybody know who invented this?).
It's in every introductory algorithms textbook; I'd be shocked if
anyone could make an IP claim on it.
> But it seems like that should buy
> back enough comparisons to justify leaving the next-run tuples out of
> the heap (unordered) until the heap becomes empty. You still want to
> insert new tuples into the heap if they can go to the current run, of
> course.
It seems like it should, but if you read (or reread) my long boring
analysis upthread, you'll learn that it doesn't. It's slower even if
the cost of building a heap is zero.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company