On Wed, Sep 7, 2016 at 2:42 PM, Tom Lane <t...@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 , 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?  https://en.wikipedia.org/wiki/Heapsort#Pseudocode -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers