This should address both Richard and Marshall's review comments, many
thanks to both!
On Fri, Jul 18, 2014 at 6:51 AM, Marshall Clow <[email protected]>
wrote:
>
> On Jul 15, 2014, at 12:18 PM, David Majnemer <[email protected]>
> wrote:
>
> > 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.
>
> I added some more bits to the tests.
> Your change to “make_heap.pass.cpp” is not right because:
> 1) It passes a comparison function to make_heap, but that test is testing
> the version that does not take a comparison predicate.
> 2) It uses a lambda, which fails when the tests are run with -std=c++03
>
> Revised test attached.
>
> — Marshall
>
>
diff --git a/include/algorithm b/include/algorithm
index 3b74a6b..3b66fa6 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -4794,49 +4794,8 @@ is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
template <class _Compare, class _RandomAccessIterator>
void
-__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, _Compare __comp,
- typename iterator_traits<_RandomAccessIterator>::difference_type __len)
-{
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
- typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
- if (__len > 1)
- {
- difference_type __p = 0;
- _RandomAccessIterator __pp = __first;
- difference_type __c = 2;
- _RandomAccessIterator __cp = __first + __c;
- if (__c == __len || __comp(*__cp, *(__cp - 1)))
- {
- --__c;
- --__cp;
- }
- if (__comp(*__pp, *__cp))
- {
- value_type __t(_VSTD::move(*__pp));
- do
- {
- *__pp = _VSTD::move(*__cp);
- __pp = __cp;
- __p = __c;
- __c = (__p + 1) * 2;
- if (__c > __len)
- break;
- __cp = __first + __c;
- if (__c == __len || __comp(*__cp, *(__cp - 1)))
- {
- --__c;
- --__cp;
- }
- } while (__comp(__t, *__cp));
- *__pp = _VSTD::move(__t);
- }
- }
-}
-
-template <class _Compare, class _RandomAccessIterator>
-void
-__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
- typename iterator_traits<_RandomAccessIterator>::difference_type __len)
+__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len)
{
typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
@@ -4869,10 +4828,10 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare
#ifdef _LIBCPP_DEBUG
typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
__debug_less<_Compare> __c(__comp);
- __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first);
+ __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
#else // _LIBCPP_DEBUG
typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
- __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - __first);
+ __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
#endif // _LIBCPP_DEBUG
}
@@ -4887,6 +4846,60 @@ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
// pop_heap
template <class _Compare, class _RandomAccessIterator>
+void
+__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len,
+ _RandomAccessIterator __start)
+{
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+ // left-child of __start is at 2 * __start + 1
+ // right-child of __start is at 2 * __start + 2
+ difference_type __child = __start - __first;
+
+ if (__len < 2 || (__len - 2) / 2 < __child)
+ return;
+
+ __child = 2 * __child + 1;
+ _RandomAccessIterator __child_i = __first + __child;
+
+ if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
+ // right-child exists and is greater than left-child
+ ++__child_i;
+ ++__child;
+ }
+
+ // check if we are in heap-order
+ if (__comp(*__child_i, *__start))
+ // we are, __start is larger than it's largest child
+ return;
+
+ value_type __top(_VSTD::move(*__start));
+ do
+ {
+ // we are not in heap-order, swap the parent with it's largest child
+ *__start = _VSTD::move(*__child_i);
+ __start = __child_i;
+
+ if ((__len - 2) / 2 < __child)
+ break;
+
+ // recompute the child based off of the updated parent
+ __child = 2 * __child + 1;
+ __child_i = __first + __child;
+
+ if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
+ // right-child exists and is greater than left-child
+ ++__child_i;
+ ++__child;
+ }
+
+ // check if we are in heap-order
+ } while (!__comp(*__child_i, __top));
+ *__start = _VSTD::move(__top);
+}
+
+template <class _Compare, class _RandomAccessIterator>
inline _LIBCPP_INLINE_VISIBILITY
void
__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
@@ -4895,7 +4908,7 @@ __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare
if (__len > 1)
{
swap(*__first, *--__last);
- __push_heap_front<_Compare>(__first, __last, __comp, __len-1);
+ __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
}
}
@@ -4932,14 +4945,15 @@ __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar
difference_type __n = __last - __first;
if (__n > 1)
{
- __last = __first;
- ++__last;
- for (difference_type __i = 1; __i < __n;)
- __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
+ // start from the first parent, there is no need to consider children
+ for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start)
+ {
+ __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
+ }
}
}
-template <class _RandomAccessIterator, class _Compare>
+template <class _Compare, class _RandomAccessIterator>
inline _LIBCPP_INLINE_VISIBILITY
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
@@ -5010,7 +5024,7 @@ __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _R
if (__comp(*__i, *__first))
{
swap(*__i, *__first);
- __push_heap_front<_Compare>(__first, __middle, __comp, __len);
+ __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
}
}
__sort_heap<_Compare>(__first, __middle, __comp);
@@ -5051,15 +5065,15 @@ __partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __r = __result_first;
if (__r != __result_last)
{
- typename iterator_traits<_RandomAccessIterator>::difference_type __len = 0;
- for (; __first != __last && __r != __result_last; ++__first, ++__r, ++__len)
+ for (; __first != __last && __r != __result_last; ++__first, ++__r)
*__r = *__first;
__make_heap<_Compare>(__result_first, __r, __comp);
+ typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
for (; __first != __last; ++__first)
if (__comp(*__first, *__result_first))
{
*__result_first = *__first;
- __push_heap_front<_Compare>(__result_first, __r, __comp, __len);
+ __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
}
__sort_heap<_Compare>(__result_first, __r, __comp);
}
diff --git a/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp b/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
index 7bbdd09..4cde1a7 100644
--- a/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
+++ b/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);
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
