15

Edit: this is not asking how to do std::make_heap the O(n) way, but rather whether this particular implementation is indeed O(n)

The textbook way of building a heap in O(n) time is to successively build the heap from bottom up. But the implementation of std::make_heap on my Mac machine in libc++ is

template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
#ifdef _LIBCPP_DEBUG
    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
    __debug_less<_Compare> __c(__comp);
    __make_heap<_Comp_ref>(__first, __last, __c);
#else  // _LIBCPP_DEBUG
    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
    __make_heap<_Comp_ref>(__first, __last, __comp);
#endif  // _LIBCPP_DEBUG
}

where __make_heap is defined as

template <class _Compare, class _RandomAccessIterator>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
    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);
    }
}

template <class _Compare, class _RandomAccessIterator>
void
__push_heap_back(_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;
    if (__len > 1)
    {
        __len = (__len - 2) / 2;
        _RandomAccessIterator __ptr = __first + __len;
        if (__comp(*__ptr, *--__last))
        {
            value_type __t(_VSTD::move(*__last));
            do
            {
                *__last = _VSTD::move(*__ptr);
                __last = __ptr;
                if (__len == 0)
                    break;
                __len = (__len - 1) / 2;
                __ptr = __first + __len;
            } while (__comp(*__ptr, __t));
            *__last = _VSTD::move(__t);
        }
    }
}

Isn't this simply iteratively inserting into the heap, thus with time complexity O(n log n)? Am I right that this is a bug?

10
  • See this answer. In short, the algorithm isn't as simple as it first seems.
    – WhozCraig
    Jun 29, 2014 at 11:44
  • @WhozCraig: I know the O(n) algorithm. I am asking whether this particular implementation (of libc++) fail to use the correct one.
    – Siyuan Ren
    Jun 29, 2014 at 12:00
  • @WhozCraig: This is in no way a duplicate question. I am not asking how to do it O(n) way. Rather, I'm asking whether this implementation is indeed O(n).
    – Siyuan Ren
    Jun 29, 2014 at 12:02
  • @Matthieu M.: See my new edit about this not being a duplicate.
    – Siyuan Ren
    Jun 29, 2014 at 12:11
  • I didn't mark it a duplicate. I linked that answer for the algorithm analysis only (which is accurate). Your question is concerning a specific implementation of that algorithm, which though related, is not a duplicate (imho) and should not have been marked as such (which is why I did not do so). Voting to reopen.
    – WhozCraig
    Jun 29, 2014 at 12:13

2 Answers 2

9

This is indeed a non-conforming O(n log n) implementation.

Comparing it to the "sift up" version of heapify from the Wikipedia article on heapsort shows that it's essentially the same algorithm. Testing it on increasing integer sequences (the worst case) gives running times that nicely fit the n log n curve, and the number of comparisons needed exceeds the standard-mandated 3n figure even for small n.

Though on the average the algorithm performs well within the 3n limit, the standard mandates worst-case performance, not the average one.

2
  • 1
    +1 thanks for finishing this. I always forget my algorithms class and worst-cast data modeling going in to the algorithm against the expect ions of the standard. Average cost on uniform random distributions seems to fit, but certainly it is a problem in their implementation for worst case. Thanks again.
    – WhozCraig
    Jun 30, 2014 at 16:11
  • 4
    Fixed in revision 213615 by David Majnemer Jul 24, 2014 at 19:12
0

I believe that the discussion here seems to have gotten off onto a tangent.

The answer to the question is: No; libc++'s implementation of std::make_heap fulfills the requirements that the C++ standard mandates for that routine.

Quoting from the C++11 standard (the upcoming C++14 standard appears to be unchanged for this)

template<class RandomAccessIterator>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

* Effects: Constructs a heap out of the range [first,last).
* Requires: The type of *first shall satisfy the MoveConstructible requirements (Table 20) and the MoveAssignable requirements (Table 22).
* Complexity: At most 3 * (last - first) comparisons.

The only complexity requirement is in terms of number of calls to the comparison operator. I have run several tests, and concluded that libc++'s implementation satisfies this requirement. I get about 2.3*N comparisons for the operation. I used the test at https://llvm.org/svn/llvm-project/libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp. @n.m, you claim otherwise; I would appreciate seeing your test cases. My tests were done with various sized arrays of ints that have been shuffled using std::random_shuffle.

The question that @WhozCraig linked to suggests that this algorithm can be implemented using significantly less than 3N comparisons. I've added that article to my (sadly, long) reading list for further study and possible improvement of libc++'s make_heap implementation. (Thanks!)

5
  • Please show your tests too so that I can verify it myself.
    – Siyuan Ren
    Jun 30, 2014 at 4:24
  • 3
    "that have been shuffled using std::random_shuffle". That's exactly the problem. The algorithm (probably) is O(n) on the average, but O(n log n) worst case. Try an ascending sequence (that's my test case). Jun 30, 2014 at 6:22
  • @n.m. you're quite right. The same test code I showed in general comment has significantly different output in worst vs average case. The gcc build on ideone (seen here) puts up numbers you would hope for. My local build using the identical toolchain and lib as the OP (output seen here) puts up enormously different numbers, easily exceeding 3N and rapidly approaching O(NlogN). You seriously should post an answer so I can uptick it. Thanks for keeping me honest. I do hereby concur it is a bugged implementation.
    – WhozCraig
    Jun 30, 2014 at 8:46
  • @n.m. I further tested the identical toolchain, switching only the standard library used from libc++ to libstdc++ from gnu, and the number are once again respectable and equivalent to those from the ideone post. Again, thanks for keeping this above water.
    – WhozCraig
    Jun 30, 2014 at 8:56
  • 1
    This answer contradicts the accepted answer. Do you agree with the assessment there, or do you still claim that libc++ satisfies the complexity constraints imposed by the standard? Jul 10, 2014 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.