On 2015-07-31 13:31:54 -0400, Robert Haas wrote:
> On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh(at)wizmail(dot)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