Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
- // + is_heap and is_heap_until in C++0x.
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
- __push_heap(_RandomAccessIterator __first,
- _Distance __holeIndex, _Distance __topIndex, _Tp __value)
- {
- _Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex && *(__first + __parent) < __value)
- {
- *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
- }
- /**
- * @brief Push an element onto a heap.
- * @param first Start of heap.
- * @param last End of heap + element.
- * @ingroup heap_algorithms
- *
- * This operation pushes the element at last-1 onto the valid heap over the
- * range [first,last-1). After completion, [first,last) is a valid heap.
- */
- template<typename _RandomAccessIterator>
- inline void
- push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
- // concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- __glibcxx_requires_valid_range(__first, __last);
- __glibcxx_requires_heap(__first, __last - 1);
- _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
- std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _GLIBCXX_MOVE(__value));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement