This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: sort_heap complexity guarantee

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

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]