On Sat, Aug 1, 2015 at 9:56 AM, Andres Freund <and...@anarazel.de> wrote: > On 2015-07-31 13:31:54 -0400, Robert Haas wrote: >> On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <j...@wizmail.org> wrote: >> > Heapification is O(n) already, whether siftup (existing) or down. >> >> That's not my impression, or what Wikipedia says. Source? > > Building a binary heap via successive insertions is O(n log n), but > building it directly is O(n). Looks like wikipedia agrees too > https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

That doesn't really address the sift-up vs. sift-down question. Maybe I'm just confused about the terminology. I think that Wikipedia article is saying that if you iterate from the middle element of an unsorted array towards the beginning, establishing the heap invariant for every item as you reach it, you will take only O(n) time. But that is not what inittapes() does. It instead starts at the beginning of the array and inserts each element one after the other. If this is any different from building the heap via successive insertions, I don't understand how. -- 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