63namespace std _GLIBCXX_VISIBILITY(default)
65_GLIBCXX_BEGIN_NAMESPACE_VERSION
72 template<
typename _RandomAccessIterator,
typename _Distance,
76 __is_heap_until(_RandomAccessIterator __first, _Distance __n,
79 _Distance __parent = 0;
80 for (_Distance __child = 1; __child < __n; ++__child)
82 if (__comp(__first + __parent, __first + __child))
84 if ((__child & 1) == 0)
92 template<
typename _RandomAccessIterator,
typename _Distance>
95 __is_heap(_RandomAccessIterator __first, _Distance __n)
97 __gnu_cxx::__ops::_Iter_less_iter __comp;
98 return std::__is_heap_until(__first, __n, __comp) == __n;
101 template<
typename _RandomAccessIterator,
typename _Compare,
105 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
107 typedef __decltype(__comp) _Cmp;
108 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
109 return std::__is_heap_until(__first, __n, __cmp) == __n;
112 template<
typename _RandomAccessIterator>
115 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
116 {
return std::__is_heap(__first,
std::distance(__first, __last)); }
118 template<
typename _RandomAccessIterator,
typename _Compare>
121 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
124 return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
131 template<
typename _RandomAccessIterator,
typename _Distance,
typename _Tp,
135 __push_heap(_RandomAccessIterator __first,
136 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
139 _Distance __parent = (__holeIndex - 1) / 2;
140 while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
142 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
143 __holeIndex = __parent;
144 __parent = (__holeIndex - 1) / 2;
146 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
159 template<
typename _RandomAccessIterator>
162 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
170 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
171 _RandomAccessIterator>)
172 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
173 __glibcxx_requires_valid_range(__first, __last);
174 __glibcxx_requires_irreflexive(__first, __last);
175 __glibcxx_requires_heap(__first, __last - 1);
177 __gnu_cxx::__ops::_Iter_less_val __comp;
178 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
179 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
180 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
195 template<
typename _RandomAccessIterator,
typename _Compare>
198 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
207 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
208 _RandomAccessIterator>)
209 __glibcxx_requires_valid_range(__first, __last);
210 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
211 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
213 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
214 __cmp(_GLIBCXX_MOVE(__comp));
215 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
216 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
217 _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
220 template<
typename _RandomAccessIterator,
typename _Distance,
221 typename _Tp,
typename _Compare>
224 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
225 _Distance __len, _Tp __value, _Compare __comp)
227 const _Distance __topIndex = __holeIndex;
228 _Distance __secondChild = __holeIndex;
229 while (__secondChild < (__len - 1) / 2)
231 __secondChild = 2 * (__secondChild + 1);
232 if (__comp(__first + __secondChild,
233 __first + (__secondChild - 1)))
235 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
236 __holeIndex = __secondChild;
238 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
240 __secondChild = 2 * (__secondChild + 1);
241 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
242 + (__secondChild - 1)));
243 __holeIndex = __secondChild - 1;
245 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
246 __cmp(_GLIBCXX_MOVE(__comp));
247 std::__push_heap(__first, __holeIndex, __topIndex,
248 _GLIBCXX_MOVE(__value), __cmp);
251 template<
typename _RandomAccessIterator,
typename _Compare>
254 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
255 _RandomAccessIterator __result, _Compare& __comp)
257 typedef typename iterator_traits<_RandomAccessIterator>::value_type
259 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
262 _ValueType __value = _GLIBCXX_MOVE(*__result);
263 *__result = _GLIBCXX_MOVE(*__first);
264 std::__adjust_heap(__first, _DistanceType(0),
265 _DistanceType(__last - __first),
266 _GLIBCXX_MOVE(__value), __comp);
280 template<
typename _RandomAccessIterator>
283 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
286 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
287 _RandomAccessIterator>)
288 __glibcxx_function_requires(_LessThanComparableConcept<
290 __glibcxx_requires_non_empty_range(__first, __last);
291 __glibcxx_requires_valid_range(__first, __last);
292 __glibcxx_requires_irreflexive(__first, __last);
293 __glibcxx_requires_heap(__first, __last);
295 if (__last - __first > 1)
298 __gnu_cxx::__ops::_Iter_less_iter __comp;
299 std::__pop_heap(__first, __last, __last, __comp);
314 template<
typename _RandomAccessIterator,
typename _Compare>
317 pop_heap(_RandomAccessIterator __first,
318 _RandomAccessIterator __last, _Compare __comp)
321 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
322 _RandomAccessIterator>)
323 __glibcxx_requires_valid_range(__first, __last);
324 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
325 __glibcxx_requires_non_empty_range(__first, __last);
326 __glibcxx_requires_heap_pred(__first, __last, __comp);
328 if (__last - __first > 1)
330 typedef __decltype(__comp) _Cmp;
331 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
333 std::__pop_heap(__first, __last, __last, __cmp);
337 template<
typename _RandomAccessIterator,
typename _Compare>
340 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
343 typedef typename iterator_traits<_RandomAccessIterator>::value_type
345 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
348 if (__last - __first < 2)
351 const _DistanceType __len = __last - __first;
352 _DistanceType __parent = (__len - 2) / 2;
355 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
356 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
372 template<
typename _RandomAccessIterator>
375 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
378 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
379 _RandomAccessIterator>)
380 __glibcxx_function_requires(_LessThanComparableConcept<
382 __glibcxx_requires_valid_range(__first, __last);
383 __glibcxx_requires_irreflexive(__first, __last);
385 __gnu_cxx::__ops::_Iter_less_iter __comp;
386 std::__make_heap(__first, __last, __comp);
399 template<
typename _RandomAccessIterator,
typename _Compare>
402 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
406 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
407 _RandomAccessIterator>)
408 __glibcxx_requires_valid_range(__first, __last);
409 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
411 typedef __decltype(__comp) _Cmp;
412 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
413 std::__make_heap(__first, __last, __cmp);
416 template<
typename _RandomAccessIterator,
typename _Compare>
419 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
422 while (__last - __first > 1)
425 std::__pop_heap(__first, __last, __last, __comp);
437 template<
typename _RandomAccessIterator>
440 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
443 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
444 _RandomAccessIterator>)
445 __glibcxx_function_requires(_LessThanComparableConcept<
447 __glibcxx_requires_valid_range(__first, __last);
448 __glibcxx_requires_irreflexive(__first, __last);
449 __glibcxx_requires_heap(__first, __last);
451 __gnu_cxx::__ops::_Iter_less_iter __comp;
452 std::__sort_heap(__first, __last, __comp);
465 template<
typename _RandomAccessIterator,
typename _Compare>
468 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
472 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
473 _RandomAccessIterator>)
474 __glibcxx_requires_valid_range(__first, __last);
475 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
476 __glibcxx_requires_heap_pred(__first, __last, __comp);
478 typedef __decltype(__comp) _Cmp;
479 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
480 std::__sort_heap(__first, __last, __cmp);
483#if __cplusplus >= 201103L
494 template<
typename _RandomAccessIterator>
495 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
496 inline _RandomAccessIterator
497 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
500 __glibcxx_function_requires(_RandomAccessIteratorConcept<
501 _RandomAccessIterator>)
502 __glibcxx_function_requires(_LessThanComparableConcept<
504 __glibcxx_requires_valid_range(__first, __last);
505 __glibcxx_requires_irreflexive(__first, __last);
507 __gnu_cxx::__ops::_Iter_less_iter __comp;
509 std::__is_heap_until(__first,
std::distance(__first, __last), __comp);
523 template<
typename _RandomAccessIterator,
typename _Compare>
524 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
525 inline _RandomAccessIterator
526 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
530 __glibcxx_function_requires(_RandomAccessIteratorConcept<
531 _RandomAccessIterator>)
532 __glibcxx_requires_valid_range(__first, __last);
533 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
535 typedef __decltype(__comp) _Cmp;
536 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
538 + std::__is_heap_until(__first,
std::distance(__first, __last), __cmp);
548 template<
typename _RandomAccessIterator>
549 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
551 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
552 {
return std::is_heap_until(__first, __last) == __last; }
562 template<
typename _RandomAccessIterator,
typename _Compare>
563 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
565 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
569 __glibcxx_function_requires(_RandomAccessIteratorConcept<
570 _RandomAccessIterator>)
571 __glibcxx_requires_valid_range(__first, __last);
572 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
575 typedef __decltype(__comp) _Cmp;
576 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
577 return std::__is_heap_until(__first, __dist, __cmp) == __dist;
581_GLIBCXX_END_NAMESPACE_VERSION
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Traits class for iterators.