Is libc++'s implementation of `std::make_heap`

问题:

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?

回答1:

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:

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!)