On 05/02/14 21:56, Robert Haas wrote:
> On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
>> The attached patch replaces the existing siftup method for heapify with
>> a siftdown method. Tested with random integers it does 18% fewer
>> compares and takes 10% less time for the heapify, over the work_mem
>> range 1024 to 1048576.
>>
>> Both algorithms appear to be O(n) (contradicting Wikipedia's claim
>> that a siftup heapify is O(n log n)).
>
> I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
> n); doing that n times is therefore O(n lg n). Your patch likewise
> implements an outer loop which runs O(n) times and an inner loop which
> runs at most O(lg n) times, so a naive analysis of that algorithm also
> comes out to O(n lg n).
The patch implements a siftdown. Measurements attached.
--
Cheers,
Jeremy