On Jul 31, 2015 4:22 AM, "Jeremy Harris" <jgh(at)wizmail(dot)org> wrote:
>
> On 30/07/15 02:05, Peter Geoghegan wrote:
> > Since heapification is now a big fraction of the total cost of a sort
> > sometimes, even where the heap invariant need not be maintained for
> > any length of time afterwards, it might be worth revisiting the patch
> > to make that an O(n) rather than a O(log n) operation [3].
>
> O(n log n) ?
>
> Heapification is O(n) already, whether siftup (existing) or down.
They are both linear on average, but the way we currently do it has an
NlogN worst case, while the other way is linear even in the worst case.
Cheers, Jeff