sort_heap complexity guarantee

[Marc Glisse]

On Sun, 5 Oct 2014, François Dumont wrote:

>    I took a look at PR 61217 regarding pop_heap complexity guarantee. Looks 
> like we have no test to check complexity of our algos so I start writing some 
> starting with the heap operations. I found no issue with make_heap, push_heap 
> and pop_heap despite what the bug report is saying however the attached 
> testcase for sort_heap is failing.
>
>    Standard is saying std::sort_heap shall use less than N * log(N) 
> comparisons but with my test using 1000 random values the test is showing:
>
> 8687 comparisons on 6907.76 max allowed
>
>    Is this a known issue of sort_heap ? Do you confirm that the test is 
> valid ?

I would first look for confirmation that the standard didn't just forget a 
big-O or something. I would expect an implementation as n calls to 
pop_heap to be legal, and if pop_heap makes 2*log(n) comparisons, that 
naively sums to too much. And I don't expect the standard to contain an 
advanced amortized analysis or anything like that...

-- 
Marc Glisse