tree eee31312877429b98be3bd240765088c40a7fbff
parent db5e54d2a33c1434441cdd39cd667fd4b83a32ac
author David Majnemer <david.majnemer@gmail.com> 1406009229 +0000
committer David Majnemer <david.majnemer@gmail.com> 1406009229 +0000

Fix std::make_heap's worst case time complexity

std::make_heap is currently implemented by iteratively applying a
siftup-type algorithm.  Since sift-up is O(ln n), this gives
std::make_heap a worst case time complexity of O(n ln n).

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.


git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@213615 91177308-0d34-0410-b5e6-96231b3b80d8