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?

Siyuan Ren
  • 7,573
  • 6
  • 47
  • 61
  • [See this answer](http://stackoverflow.com/a/6300047/1322972). In short, the algorithm isn't as simple as it first seems. – WhozCraig Jun 29 '14 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 '14 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 '14 at 12:02
  • @Matthieu M.: See my new edit about this not being a duplicate. – Siyuan Ren Jun 29 '14 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 '14 at 12:13
  • @C.R.: I hesitated to mark it as duplicate as well; and to be honest I still hesitate. The fact is, the algorithm here seems awfully similar to the other one, for which the analysis proved it was O(n). There are some differences, certainly, but it seems to me they are not game changing. – Matthieu M. Jun 29 '14 at 12:18
  • @MatthieuM. I concur as well, I was really on the fence to dupe this, but chose not to because that implementation, though similar, is not the same as this question. The answer I linked (from that question, and which I believe is the correct answer to said-same even though the OP there seemed to choose a different one) is a beautiful algorithm analysis. I believe that analysis fits this implementation as well, and that may be all C.R. is really looking to validate. – WhozCraig Jun 29 '14 at 12:20
  • This indeed looks like the wrong version of the algorithm, and I have measure its operation count for various input sizes and it seems to fit the `n log n` curve. – n. m. could be an AI Jun 29 '14 at 13:00
  • I have Xcode 5.1.1 running the identical libc++ implementation you are, and the analysis from the linked answer regarding the algorithm appears accurate. I wrote a simple test-jig of making heaps from randomly generated sequences fro 1024 to 102400 in length, the gcc version can be [seen here](http://ideone.com/cgeeCZ). The release-output from my mac can be [seen here](http://pastebin.com/KnfZxEQr). The output includes N, NlogN, 3*N, and the actual comparisons performed. At no time was 3N exceeded (or even met). Hope it helps. – WhozCraig Jun 29 '14 at 22:53
  • Edit: After reading n.m's comments below I forged ahead and tested worst-case rather than average-case complexity, and indeed he is correct. [See my comment](http://stackoverflow.com/questions/24475056/is-libcs-implementation-of-stdmake-heap-nonconformant/24482515#comment37902684_24482515) for further info. – WhozCraig Jun 30 '14 at 08:51

2 Answers2

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.

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
  • @C.R. Thanks for filing the bug. – Marshall Clow Jun 30 '14 at 14:04
  • 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 '14 at 16:11
  • 4
    Fixed in revision 213615 by David Majnemer – Marshall Clow Jul 24 '14 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!)

Marshall Clow
  • 15,972
  • 2
  • 29
  • 45
  • Please show your tests too so that I can verify it myself. – Siyuan Ren Jun 30 '14 at 04: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). – n. m. could be an AI Jun 30 '14 at 06: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](http://ideone.com/A1i2e6)) puts up numbers you would hope for. My local build using the identical toolchain and lib as the OP ([output seen here](http://pastebin.com/5h05htHR)) 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 '14 at 08: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 '14 at 08: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? – user4815162342 Jul 10 '14 at 06:24