62 namespace std _GLIBCXX_VISIBILITY(default)
64 _GLIBCXX_BEGIN_NAMESPACE_VERSION
71 template<
typename _RandomAccessIterator,
typename _Distance,
74 __is_heap_until(_RandomAccessIterator __first, _Distance __n,
77 _Distance __parent = 0;
78 for (_Distance __child = 1; __child < __n; ++__child)
80 if (__comp(__first + __parent, __first + __child))
82 if ((__child & 1) == 0)
90 template<
typename _RandomAccessIterator,
typename _Distance>
92 __is_heap(_RandomAccessIterator __first, _Distance __n)
94 __gnu_cxx::__ops::_Iter_less_iter __comp;
95 return std::__is_heap_until(__first, __n, __comp) == __n;
98 template<
typename _RandomAccessIterator,
typename _Compare,
101 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
103 __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
104 return std::__is_heap_until(__first, __n, __cmp) == __n;
107 template<
typename _RandomAccessIterator>
109 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
110 {
return std::__is_heap(__first,
std::distance(__first, __last)); }
112 template<
typename _RandomAccessIterator,
typename _Compare>
114 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
117 return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
124 template<
typename _RandomAccessIterator,
typename _Distance,
typename _Tp,
127 __push_heap(_RandomAccessIterator __first,
128 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
131 _Distance __parent = (__holeIndex - 1) / 2;
132 while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
134 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
135 __holeIndex = __parent;
136 __parent = (__holeIndex - 1) / 2;
138 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
151 template<
typename _RandomAccessIterator>
153 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
155 typedef typename iterator_traits<_RandomAccessIterator>::value_type
157 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
161 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
162 _RandomAccessIterator>)
163 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
164 __glibcxx_requires_valid_range(__first, __last);
165 __glibcxx_requires_irreflexive(__first, __last);
166 __glibcxx_requires_heap(__first, __last - 1);
168 __gnu_cxx::__ops::_Iter_less_val __comp;
169 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
170 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
171 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
186 template<
typename _RandomAccessIterator,
typename _Compare>
188 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
191 typedef typename iterator_traits<_RandomAccessIterator>::value_type
193 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
197 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
198 _RandomAccessIterator>)
199 __glibcxx_requires_valid_range(__first, __last);
200 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
201 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
203 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
204 __cmp(_GLIBCXX_MOVE(__comp));
205 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
206 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
207 _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
210 template<
typename _RandomAccessIterator,
typename _Distance,
211 typename _Tp,
typename _Compare>
213 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
214 _Distance __len, _Tp __value, _Compare __comp)
216 const _Distance __topIndex = __holeIndex;
217 _Distance __secondChild = __holeIndex;
218 while (__secondChild < (__len - 1) / 2)
220 __secondChild = 2 * (__secondChild + 1);
221 if (__comp(__first + __secondChild,
222 __first + (__secondChild - 1)))
224 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
225 __holeIndex = __secondChild;
227 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
229 __secondChild = 2 * (__secondChild + 1);
230 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
231 + (__secondChild - 1)));
232 __holeIndex = __secondChild - 1;
234 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
235 __cmp(_GLIBCXX_MOVE(__comp));
236 std::__push_heap(__first, __holeIndex, __topIndex,
237 _GLIBCXX_MOVE(__value), __cmp);
240 template<
typename _RandomAccessIterator,
typename _Compare>
242 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
243 _RandomAccessIterator __result, _Compare& __comp)
245 typedef typename iterator_traits<_RandomAccessIterator>::value_type
247 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
250 _ValueType __value = _GLIBCXX_MOVE(*__result);
251 *__result = _GLIBCXX_MOVE(*__first);
252 std::__adjust_heap(__first, _DistanceType(0),
253 _DistanceType(__last - __first),
254 _GLIBCXX_MOVE(__value), __comp);
268 template<
typename _RandomAccessIterator>
270 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
273 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
274 _RandomAccessIterator>)
275 __glibcxx_function_requires(_LessThanComparableConcept<
276 typename iterator_traits<_RandomAccessIterator>::value_type>)
277 __glibcxx_requires_non_empty_range(__first, __last);
278 __glibcxx_requires_valid_range(__first, __last);
279 __glibcxx_requires_irreflexive(__first, __last);
280 __glibcxx_requires_heap(__first, __last);
282 if (__last - __first > 1)
285 __gnu_cxx::__ops::_Iter_less_iter __comp;
286 std::__pop_heap(__first, __last, __last, __comp);
301 template<
typename _RandomAccessIterator,
typename _Compare>
303 pop_heap(_RandomAccessIterator __first,
304 _RandomAccessIterator __last, _Compare __comp)
307 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
308 _RandomAccessIterator>)
309 __glibcxx_requires_valid_range(__first, __last);
310 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
311 __glibcxx_requires_non_empty_range(__first, __last);
312 __glibcxx_requires_heap_pred(__first, __last, __comp);
314 if (__last - __first > 1)
316 using __gnu_cxx::__ops::_Iter_comp_iter;
317 _Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
319 std::__pop_heap(__first, __last, __last, __cmp);
323 template<
typename _RandomAccessIterator,
typename _Compare>
325 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
328 typedef typename iterator_traits<_RandomAccessIterator>::value_type
330 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
333 if (__last - __first < 2)
336 const _DistanceType __len = __last - __first;
337 _DistanceType __parent = (__len - 2) / 2;
340 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
341 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
357 template<
typename _RandomAccessIterator>
359 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
362 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
363 _RandomAccessIterator>)
364 __glibcxx_function_requires(_LessThanComparableConcept<
365 typename iterator_traits<_RandomAccessIterator>::value_type>)
366 __glibcxx_requires_valid_range(__first, __last);
367 __glibcxx_requires_irreflexive(__first, __last);
369 __gnu_cxx::__ops::_Iter_less_iter __comp;
370 std::__make_heap(__first, __last, __comp);
383 template<
typename _RandomAccessIterator,
typename _Compare>
385 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
389 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
390 _RandomAccessIterator>)
391 __glibcxx_requires_valid_range(__first, __last);
392 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
394 __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
395 std::__make_heap(__first, __last, __cmp);
398 template<
typename _RandomAccessIterator,
typename _Compare>
400 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
403 while (__last - __first > 1)
406 std::__pop_heap(__first, __last, __last, __comp);
418 template<
typename _RandomAccessIterator>
420 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
423 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
424 _RandomAccessIterator>)
425 __glibcxx_function_requires(_LessThanComparableConcept<
426 typename iterator_traits<_RandomAccessIterator>::value_type>)
427 __glibcxx_requires_valid_range(__first, __last);
428 __glibcxx_requires_irreflexive(__first, __last);
429 __glibcxx_requires_heap(__first, __last);
431 __gnu_cxx::__ops::_Iter_less_iter __comp;
432 std::__sort_heap(__first, __last, __comp);
445 template<
typename _RandomAccessIterator,
typename _Compare>
447 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
451 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
452 _RandomAccessIterator>)
453 __glibcxx_requires_valid_range(__first, __last);
454 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
455 __glibcxx_requires_heap_pred(__first, __last, __comp);
457 __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
458 std::__sort_heap(__first, __last, __cmp);
461 #if __cplusplus >= 201103L 472 template<
typename _RandomAccessIterator>
473 inline _RandomAccessIterator
474 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
477 __glibcxx_function_requires(_RandomAccessIteratorConcept<
478 _RandomAccessIterator>)
479 __glibcxx_function_requires(_LessThanComparableConcept<
480 typename iterator_traits<_RandomAccessIterator>::value_type>)
481 __glibcxx_requires_valid_range(__first, __last);
482 __glibcxx_requires_irreflexive(__first, __last);
484 __gnu_cxx::__ops::_Iter_less_iter __comp;
486 std::__is_heap_until(__first,
std::distance(__first, __last), __comp);
500 template<
typename _RandomAccessIterator,
typename _Compare>
501 inline _RandomAccessIterator
502 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
506 __glibcxx_function_requires(_RandomAccessIteratorConcept<
507 _RandomAccessIterator>)
508 __glibcxx_requires_valid_range(__first, __last);
509 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
511 __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
513 + std::__is_heap_until(__first,
std::distance(__first, __last), __cmp);
523 template<
typename _RandomAccessIterator>
525 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
536 template<
typename _RandomAccessIterator,
typename _Compare>
538 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
542 __glibcxx_function_requires(_RandomAccessIteratorConcept<
543 _RandomAccessIterator>)
544 __glibcxx_requires_valid_range(__first, __last);
545 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
548 __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
549 return std::__is_heap_until(__first, __dist, __cmp) == __dist;
553 _GLIBCXX_END_NAMESPACE_VERSION
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Search the end of a heap using comparison functor.