การใช้ `std::make_heap` ของ libc++ ไม่สอดคล้องกันหรือไม่

แก้ไข: นี่ไม่ใช่การถามว่าจะทำอย่างไร std::make_heap วิธี O(n) แต่ถามว่าการใช้งานเฉพาะนี้เป็น O(n) จริงหรือไม่

วิธีการสร้างฮีปตามตำราเรียนในเวลา O(n) คือการสร้างฮีปอย่างต่อเนื่องจากล่างขึ้นบน แต่การใช้งาน std::make_heap บนเครื่อง Mac ของฉันใน libc++ คือ

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) หรือไม่? ฉันพูดถูกไหมว่านี่เป็นข้อผิดพลาด?