Re: Is tuplesort_heap_siftup() a misnomer?

On Fri, Aug 12, 2016 at 4:30 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Doesn't tuplesort_heap_siftup() actually shift-down?
>
> The Wikipedia article on heaps [1] lists "shift-down" (never "sift
> down", FWIW) as a common operation on a heap:
>
> "shift-down: move a node down in the tree, similar to shift-up; used
> to restore heap condition after deletion or replacement."
>
> This seems to be what tuplesort_heap_siftup() actually does (among
> other things; its job is to compact the heap following caller
> returning the root, where caller leaves a "hole" at the root position
> 0).

Heikki (CC'd) and I discussed this privately today, and we were in
agreement that this needs to be fixed, so I wrote a patch, which I
attach here.

--
Peter Geoghegan