是libc ++的`std :: make_heap`的实现不符合 [英] Is libc++'s implementation of `std::make_heap` nonconformant

问题描述

编辑：这不是问如何做 std :: make_heap O（n）的方式，而是这个特定的实现是否确实O ）

在O（n）时间构建堆的教科书方法是从下往上连续构建堆。但在我的Mac机器上在libc ++中的 std :: make_heap 的实现是

  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 
} 
  

其中 __make_heap 定义为

  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）; 
} 
} 
} 
  

插入堆，因此具有时间复杂度O（n log n）？

解决方案

这确实是一个不合格的O（n log n）实现。 / p>

将它与维基百科中的sift up版本的heapify进行比较关于堆栈的文章表明它本质上是相同的算法。在增加整数序列（最坏情况）下测试它的运行时间非常适合 n log n 曲线，并且所需的比较数超过标准命令 3n ，即使对于小 n 也是如此。

虽然平均算法在 3n 限制内运行良好，但标准要求最坏情况下的性能，平均一个。

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?

解决方案

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.

这篇关于是libc ++的`std :: make_heap`的实现不符合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！