Ping.
On Wed, Jul 9, 2014 at 3:14 AM, David Majnemer <[email protected]> wrote: > std::make_heap is currently implemented by iteratively applying a > sift_up-type algorithm. > Since sift-up is O(ln n), this gives std::make_heap a worst case time > complexity of O(n ln n). Since the C++ standard mandates that > std::make_heap make no more than O(3n) comparisons, this makes our > std::make_heap out of spec. > > Fix this by introducing an implementation of __sift_down and switch > std::make_heap to create the heap using it. This gives std::make_heap > linear time complexity in the worst case. > > This fixes PR20161. _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
