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 I'm pretty sure that there's a bunch of places where we intentionally build a heap at once instead successively. At least reorderbuffer.c does so, and it looks like nodeMergeAppend as well (that's why they use binaryheap_add_unordered and then binaryheap_build). Greetings, Andres Freund -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
