On Tue, Mar 20, 2012 at 12:12 PM, Tom Lane <t...@sss.pgh.pa.us> wrote:
> Greg Stark <st...@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

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to