мотрел на стандарт C ++ 0x и обнаружил, что make_heap должен выполнять не более 3 * N сравнений.

То есть Сформировать неупорядоченную коллекцию можно в O (N)

   /*  @brief  Construct a heap over a range using comparison functor.

Почему это?

Источник не дает мне никаких подсказок (g ++ 4.4.3)

While (true) + __parent == 0 - это не подсказки, а предположение о поведении O (N)

template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
{

  const _DistanceType __len = __last - __first;
  _DistanceType __parent = (__len - 2) / 2;
  while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
}

__adjust_heap выглядит как метод log N:

while ( __secondChild < (__len - 1) / 2)
{
    __secondChild = 2 * (__secondChild + 1);

Для меня это болотный стандартный журнал.

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
          _Distance __len, _Tp __value, _Compare __comp)
    {
      const _Distance __topIndex = __holeIndex;
      _Distance __secondChild = __holeIndex;
      while (__secondChild < (__len - 1) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
          if (__comp(*(__first + __secondChild),
             *(__first + (__secondChild - 1))))
          __secondChild--;
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
          __holeIndex = __secondChild;
      }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
        *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             + (__secondChild - 1)));
        __holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, 
               _GLIBCXX_MOVE(__value), __comp);      
      }

Любые подсказки, почему это O <= 3N, будут оценены.
РЕДАКТИРОВАТЬ:

Результаты эксперимента:

Эта фактическая реализация использует

<2N сравнений для куч кучи<1,5 Н для куч кучи в обратном порядке.