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.
PR20161.patch
Description: Binary data
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
