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.

llvm-svn: 213615

1 files changed, 22 insertions, 1 deletions

diff --git a/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp b/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
index 7bbdd09546c..4cde1a7d32e 100644
--- a/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
+++ b/libcxx/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
@@ -35,14 +35,35 @@ struct indirect_less
 void test(unsigned N)
 {
     int* ia = new int [N];
+    {
     for (int i = 0; i < N; ++i)
         ia[i] = i;
-    {
     std::random_shuffle(ia, ia+N);
     std::make_heap(ia, ia+N, std::greater<int>());
     assert(std::is_heap(ia, ia+N, std::greater<int>()));
     }
 
+//  Ascending
+    {
+    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
+    for (int i = 0; i < N; ++i)
+        ia[i] = i;
+    std::make_heap(ia, ia+N, std::ref(pred));
+    assert(pred.count() <= 3*N);
+    assert(std::is_heap(ia, ia+N, pred));
+    }
+
+//  Descending
+    {
+    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
+    for (int i = 0; i < N; ++i)
+        ia[N-1-i] = i;
+    std::make_heap(ia, ia+N, std::ref(pred));
+    assert(pred.count() <= 3*N);
+    assert(std::is_heap(ia, ia+N, pred));
+    }
+
+//  Random
     {
     binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
     std::random_shuffle(ia, ia+N);