Peter Geoghegan <pg@heroku.com> writes:
> On Thu, Sep 8, 2016 at 12:01 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:
>> I still think tuplesort_heap_siftup is a confusing name, although I'm not
>> sure that Peter's "compact" is much better. I suggest that we rename it to
>> tuplesort_heap_delete_top(). In comments within the function, explain that
>> the *loop* corresponds to the "siftup" in Knuth's book.
> I'm also fine with that name.
I can live with it too.
>> Interestingly, as Knuth explains the siftup algorithm, it performs a
>> "replace the top" operation, rather than "remove the top". But we use it to
>> remove the top, by moving the last element to the top and running the
>> algorithm after that. Peter's other patch, to change the way we currently
>> replace the top node, to do it in one pass rather than as delete+insert, is
>> actually Knuth's siftup algorithm.
> Knuth must have a strange sense of humor.
I'm too lazy to get the book back down off the shelf to check, but I think
that Knuth uses sift-up to describe two different algorithms that have
essentially the same inner loop.
regards, tom lane