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: http://www.postgresql.org/mailpref/pgsql-hackers
