On Wed, Sep 7, 2016 at 2:42 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> The reason it's called siftup is that that's what Knuth calls it.
> See Algorithm 5.2.3H (Heapsort), pp 146-147 in the first edition of
> Volume 3; tuplesort_heap_siftup corresponds directly to steps H3-H8.
I see that Knuth explains that these steps form the siftup procedure.
What steps does tuplesort_heap_insert correspond to, if any?
5.2.3.H is about heapsort, and so the Wikipedia article on heapsort
(not the one on heaps in general, which I referenced first) may be a
useful reference here. It's also freely available. Consider the
Wikipedia pseudocode for siftup [1], from classic heapsort. That
version goes from child to parent each iteration (in the first
iteration, "child" is initialized to "end" -- not root). So, it
*ascends* the heap ("child" is assigned from "parent" for any
subsequent iterations). OTOH, tuplesort_heap_siftup always starts from
the root of tuplesort's top-level heap (or the "hole" at the root
position, if you prefer), and *descends* the heap.
> I think this patch is misguided, as it unnecessarily moves the code
> away from standard nomenclature.
As I mentioned, the patch is guided by the descriptions of fundamental
operations on heaps from Wikipedia (I didn't think much about heapsort
until now). I'm not really proposing to change things in a way that is
inconsistent with Knuth (regardless of how the term siftup is
understood). I'm proposing to change things in a way that seems
clearer overall, particularly given the way that these various
routines are used in fairly distinct contexts.
The terminology in this area can be confusing. My Sedgewick/Wayne
Algorithms book never uses the term shift or sift when discussing
heaps, even once in passing. The call shift up "swim", and shift down
"sink", possibly because they'd like to avoid any baggage that other
terminology has.
I propose, as a compromise, to not introduce the term "shift down" at
all in this patch, but to still rename tuplesort_heap_siftup to
tuplesort_heap_compact. Even assuming that I'm wrong about siftup
here, I think that that still represents an improvement. Would that be
acceptable to you?
[1] https://en.wikipedia.org/wiki/Heapsort#Pseudocode
--
Peter Geoghegan