Edit Question - KnowledgeHub

Title Body

I looked in to the C++0x standard and found the requirement that make_heap should do no more than 3*N comparisons. I.e. heapify an unordered collection can be done in O(N) /* @brief Construct a heap over a range using comparison functor. Why is this? The source gives me no clues (g++ 4.4.3) The while (true) + __parent == 0 are not clues but rather a guess for O(N) behaviour 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 looks like a log N method: while ( __secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); Is a bog standard log N to me. 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) {

Tags (comma-separated) Cancel