Branch data Line data Source code
1 : : // Heap implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 : : // Free Software Foundation, Inc.
5 : : //
6 : : // This file is part of the GNU ISO C++ Library. This library is free
7 : : // software; you can redistribute it and/or modify it under the
8 : : // terms of the GNU General Public License as published by the
9 : : // Free Software Foundation; either version 2, or (at your option)
10 : : // any later version.
11 : :
12 : : // This library is distributed in the hope that it will be useful,
13 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : // GNU General Public License for more details.
16 : :
17 : : // You should have received a copy of the GNU General Public License along
18 : : // with this library; see the file COPYING. If not, write to the Free
19 : : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : : // USA.
21 : :
22 : : // As a special exception, you may use this file as part of a free software
23 : : // library without restriction. Specifically, if other files instantiate
24 : : // templates or use macros or inline functions from this file, or you compile
25 : : // this file and link it with other files to produce an executable, this
26 : : // file does not by itself cause the resulting executable to be covered by
27 : : // the GNU General Public License. This exception does not however
28 : : // invalidate any other reasons why the executable file might be covered by
29 : : // the GNU General Public License.
30 : :
31 : : /*
32 : : *
33 : : * Copyright (c) 1994
34 : : * Hewlett-Packard Company
35 : : *
36 : : * Permission to use, copy, modify, distribute and sell this software
37 : : * and its documentation for any purpose is hereby granted without fee,
38 : : * provided that the above copyright notice appear in all copies and
39 : : * that both that copyright notice and this permission notice appear
40 : : * in supporting documentation. Hewlett-Packard Company makes no
41 : : * representations about the suitability of this software for any
42 : : * purpose. It is provided "as is" without express or implied warranty.
43 : : *
44 : : * Copyright (c) 1997
45 : : * Silicon Graphics Computer Systems, Inc.
46 : : *
47 : : * Permission to use, copy, modify, distribute and sell this software
48 : : * and its documentation for any purpose is hereby granted without fee,
49 : : * provided that the above copyright notice appear in all copies and
50 : : * that both that copyright notice and this permission notice appear
51 : : * in supporting documentation. Silicon Graphics makes no
52 : : * representations about the suitability of this software for any
53 : : * purpose. It is provided "as is" without express or implied warranty.
54 : : */
55 : :
56 : : /** @file stl_heap.h
57 : : * This is an internal header file, included by other library headers.
58 : : * You should not attempt to use it directly.
59 : : */
60 : :
61 : : #ifndef _STL_HEAP_H
62 : : #define _STL_HEAP_H 1
63 : :
64 : : #include <debug/debug.h>
65 : : #include <bits/stl_move.h>
66 : :
67 : : _GLIBCXX_BEGIN_NAMESPACE(std)
68 : :
69 : : template<typename _RandomAccessIterator, typename _Distance>
70 : : _Distance
71 : : __is_heap_until(_RandomAccessIterator __first, _Distance __n)
72 : : {
73 : : _Distance __parent = 0;
74 : : for (_Distance __child = 1; __child < __n; ++__child)
75 : : {
76 : : if (__first[__parent] < __first[__child])
77 : : return __child;
78 : : if ((__child & 1) == 0)
79 : : ++__parent;
80 : : }
81 : : return __n;
82 : : }
83 : :
84 : : template<typename _RandomAccessIterator, typename _Distance,
85 : : typename _Compare>
86 : : _Distance
87 : : __is_heap_until(_RandomAccessIterator __first, _Distance __n,
88 : : _Compare __comp)
89 : : {
90 : : _Distance __parent = 0;
91 : : for (_Distance __child = 1; __child < __n; ++__child)
92 : : {
93 : : if (__comp(__first[__parent], __first[__child]))
94 : : return __child;
95 : : if ((__child & 1) == 0)
96 : : ++__parent;
97 : : }
98 : : return __n;
99 : : }
100 : :
101 : : // __is_heap, a predicate testing whether or not a range is a heap.
102 : : // This function is an extension, not part of the C++ standard.
103 : : template<typename _RandomAccessIterator, typename _Distance>
104 : : inline bool
105 : : __is_heap(_RandomAccessIterator __first, _Distance __n)
106 : : { return std::__is_heap_until(__first, __n) == __n; }
107 : :
108 : : template<typename _RandomAccessIterator, typename _Compare,
109 : : typename _Distance>
110 : : inline bool
111 : : __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
112 : : { return std::__is_heap_until(__first, __n, __comp) == __n; }
113 : :
114 : : template<typename _RandomAccessIterator>
115 : : inline bool
116 : : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
117 : : { return std::__is_heap(__first, std::distance(__first, __last)); }
118 : :
119 : : template<typename _RandomAccessIterator, typename _Compare>
120 : : inline bool
121 : : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
122 : : _Compare __comp)
123 : : { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
124 : :
125 : : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
126 : : // + is_heap and is_heap_until in C++0x.
127 : :
128 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
129 : : void
130 : : __push_heap(_RandomAccessIterator __first,
131 : : _Distance __holeIndex, _Distance __topIndex, _Tp __value)
132 : : {
133 : : _Distance __parent = (__holeIndex - 1) / 2;
134 : : while (__holeIndex > __topIndex && *(__first + __parent) < __value)
135 : : {
136 : : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
137 : : __holeIndex = __parent;
138 : : __parent = (__holeIndex - 1) / 2;
139 : : }
140 : : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
141 : : }
142 : :
143 : : /**
144 : : * @brief Push an element onto a heap.
145 : : * @param first Start of heap.
146 : : * @param last End of heap + element.
147 : : * @ingroup heap
148 : : *
149 : : * This operation pushes the element at last-1 onto the valid heap over the
150 : : * range [first,last-1). After completion, [first,last) is a valid heap.
151 : : */
152 : : template<typename _RandomAccessIterator>
153 : : inline void
154 : : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
155 : : {
156 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
157 : : _ValueType;
158 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
159 : : _DistanceType;
160 : :
161 : : // concept requirements
162 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
163 : : _RandomAccessIterator>)
164 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
165 : : __glibcxx_requires_valid_range(__first, __last);
166 : : __glibcxx_requires_heap(__first, __last - 1);
167 : :
168 : : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
169 : : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
170 : : _DistanceType(0), _GLIBCXX_MOVE(__value));
171 : : }
172 : :
173 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
174 : : typename _Compare>
175 : : void
176 : : __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
177 : 0 : _Distance __topIndex, _Tp __value, _Compare __comp)
178 : : {
179 : 0 : _Distance __parent = (__holeIndex - 1) / 2;
180 [ # # ][ # # ]: 0 : while (__holeIndex > __topIndex
[ # # ][ # # ]
[ # # ][ # # ]
181 : : && __comp(*(__first + __parent), __value))
182 : : {
183 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
184 : 0 : __holeIndex = __parent;
185 : 0 : __parent = (__holeIndex - 1) / 2;
186 : : }
187 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
188 : 0 : }
189 : :
190 : : /**
191 : : * @brief Push an element onto a heap using comparison functor.
192 : : * @param first Start of heap.
193 : : * @param last End of heap + element.
194 : : * @param comp Comparison functor.
195 : : * @ingroup heap
196 : : *
197 : : * This operation pushes the element at last-1 onto the valid heap over the
198 : : * range [first,last-1). After completion, [first,last) is a valid heap.
199 : : * Compare operations are performed using comp.
200 : : */
201 : : template<typename _RandomAccessIterator, typename _Compare>
202 : : inline void
203 : : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
204 : : _Compare __comp)
205 : : {
206 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
207 : : _ValueType;
208 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
209 : : _DistanceType;
210 : :
211 : : // concept requirements
212 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
213 : : _RandomAccessIterator>)
214 : : __glibcxx_requires_valid_range(__first, __last);
215 : : __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
216 : :
217 : : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
218 : : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
219 : : _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
220 : : }
221 : :
222 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
223 : : void
224 : : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
225 : : _Distance __len, _Tp __value)
226 : : {
227 : : const _Distance __topIndex = __holeIndex;
228 : : _Distance __secondChild = __holeIndex;
229 : : while (__secondChild < (__len - 1) / 2)
230 : : {
231 : : __secondChild = 2 * (__secondChild + 1);
232 : : if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
233 : : __secondChild--;
234 : : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
235 : : __holeIndex = __secondChild;
236 : : }
237 : : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
238 : : {
239 : : __secondChild = 2 * (__secondChild + 1);
240 : : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
241 : : + (__secondChild - 1)));
242 : : __holeIndex = __secondChild - 1;
243 : : }
244 : : std::__push_heap(__first, __holeIndex, __topIndex,
245 : : _GLIBCXX_MOVE(__value));
246 : : }
247 : :
248 : : template<typename _RandomAccessIterator>
249 : : inline void
250 : : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
251 : : _RandomAccessIterator __result)
252 : : {
253 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
254 : : _ValueType;
255 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
256 : : _DistanceType;
257 : :
258 : : _ValueType __value = _GLIBCXX_MOVE(*__result);
259 : : *__result = _GLIBCXX_MOVE(*__first);
260 : : std::__adjust_heap(__first, _DistanceType(0),
261 : : _DistanceType(__last - __first),
262 : : _GLIBCXX_MOVE(__value));
263 : : }
264 : :
265 : : /**
266 : : * @brief Pop an element off a heap.
267 : : * @param first Start of heap.
268 : : * @param last End of heap.
269 : : * @ingroup heap
270 : : *
271 : : * This operation pops the top of the heap. The elements first and last-1
272 : : * are swapped and [first,last-1) is made into a heap.
273 : : */
274 : : template<typename _RandomAccessIterator>
275 : : inline void
276 : : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
277 : : {
278 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
279 : : _ValueType;
280 : :
281 : : // concept requirements
282 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
283 : : _RandomAccessIterator>)
284 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
285 : : __glibcxx_requires_valid_range(__first, __last);
286 : : __glibcxx_requires_heap(__first, __last);
287 : :
288 : : std::__pop_heap(__first, __last - 1, __last - 1);
289 : : }
290 : :
291 : : template<typename _RandomAccessIterator, typename _Distance,
292 : : typename _Tp, typename _Compare>
293 : : void
294 : : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
295 : 0 : _Distance __len, _Tp __value, _Compare __comp)
296 : : {
297 : 0 : const _Distance __topIndex = __holeIndex;
298 : 0 : _Distance __secondChild = __holeIndex;
299 [ # # ]: 0 : while (__secondChild < (__len - 1) / 2)
300 : : {
301 : 0 : __secondChild = 2 * (__secondChild + 1);
302 [ # # ]: 0 : if (__comp(*(__first + __secondChild),
303 : : *(__first + (__secondChild - 1))))
304 : 0 : __secondChild--;
305 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
306 : 0 : __holeIndex = __secondChild;
307 : : }
308 [ # # ][ # # ]: 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
309 : : {
310 : 0 : __secondChild = 2 * (__secondChild + 1);
311 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
312 : : + (__secondChild - 1)));
313 : 0 : __holeIndex = __secondChild - 1;
314 : : }
315 : 0 : std::__push_heap(__first, __holeIndex, __topIndex,
316 : : _GLIBCXX_MOVE(__value), __comp);
317 : 0 : }
318 : :
319 : : template<typename _RandomAccessIterator, typename _Compare>
320 : : inline void
321 : : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
322 : 0 : _RandomAccessIterator __result, _Compare __comp)
323 : : {
324 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
325 : : _ValueType;
326 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
327 : : _DistanceType;
328 : :
329 : : _ValueType __value = _GLIBCXX_MOVE(*__result);
330 : : *__result = _GLIBCXX_MOVE(*__first);
331 : 0 : std::__adjust_heap(__first, _DistanceType(0),
332 : : _DistanceType(__last - __first),
333 : : _GLIBCXX_MOVE(__value), __comp);
334 : 0 : }
335 : :
336 : : /**
337 : : * @brief Pop an element off a heap using comparison functor.
338 : : * @param first Start of heap.
339 : : * @param last End of heap.
340 : : * @param comp Comparison functor to use.
341 : : * @ingroup heap
342 : : *
343 : : * This operation pops the top of the heap. The elements first and last-1
344 : : * are swapped and [first,last-1) is made into a heap. Comparisons are
345 : : * made using comp.
346 : : */
347 : : template<typename _RandomAccessIterator, typename _Compare>
348 : : inline void
349 : : pop_heap(_RandomAccessIterator __first,
350 : : _RandomAccessIterator __last, _Compare __comp)
351 : : {
352 : : // concept requirements
353 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
354 : : _RandomAccessIterator>)
355 : : __glibcxx_requires_valid_range(__first, __last);
356 : : __glibcxx_requires_heap_pred(__first, __last, __comp);
357 : :
358 : 0 : std::__pop_heap(__first, __last - 1, __last - 1, __comp);
359 : : }
360 : :
361 : : /**
362 : : * @brief Construct a heap over a range.
363 : : * @param first Start of heap.
364 : : * @param last End of heap.
365 : : * @ingroup heap
366 : : *
367 : : * This operation makes the elements in [first,last) into a heap.
368 : : */
369 : : template<typename _RandomAccessIterator>
370 : : void
371 : : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
372 : : {
373 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
374 : : _ValueType;
375 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
376 : : _DistanceType;
377 : :
378 : : // concept requirements
379 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
380 : : _RandomAccessIterator>)
381 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
382 : : __glibcxx_requires_valid_range(__first, __last);
383 : :
384 : : if (__last - __first < 2)
385 : : return;
386 : :
387 : : const _DistanceType __len = __last - __first;
388 : : _DistanceType __parent = (__len - 2) / 2;
389 : : while (true)
390 : : {
391 : : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
392 : : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
393 : : if (__parent == 0)
394 : : return;
395 : : __parent--;
396 : : }
397 : : }
398 : :
399 : : /**
400 : : * @brief Construct a heap over a range using comparison functor.
401 : : * @param first Start of heap.
402 : : * @param last End of heap.
403 : : * @param comp Comparison functor to use.
404 : : * @ingroup heap
405 : : *
406 : : * This operation makes the elements in [first,last) into a heap.
407 : : * Comparisons are made using comp.
408 : : */
409 : : template<typename _RandomAccessIterator, typename _Compare>
410 : : void
411 : : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
412 : 0 : _Compare __comp)
413 : : {
414 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
415 : : _ValueType;
416 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
417 : : _DistanceType;
418 : :
419 : : // concept requirements
420 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
421 : : _RandomAccessIterator>)
422 : : __glibcxx_requires_valid_range(__first, __last);
423 : :
424 [ # # ]: 0 : if (__last - __first < 2)
425 : 0 : return;
426 : :
427 : 0 : const _DistanceType __len = __last - __first;
428 : 0 : _DistanceType __parent = (__len - 2) / 2;
429 : 0 : while (true)
430 : : {
431 : 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
432 : 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
433 : : __comp);
434 [ # # ]: 0 : if (__parent == 0)
435 : 0 : return;
436 : 0 : __parent--;
437 : : }
438 : : }
439 : :
440 : : /**
441 : : * @brief Sort a heap.
442 : : * @param first Start of heap.
443 : : * @param last End of heap.
444 : : * @ingroup heap
445 : : *
446 : : * This operation sorts the valid heap in the range [first,last).
447 : : */
448 : : template<typename _RandomAccessIterator>
449 : : void
450 : : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
451 : : {
452 : : // concept requirements
453 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
454 : : _RandomAccessIterator>)
455 : : __glibcxx_function_requires(_LessThanComparableConcept<
456 : : typename iterator_traits<_RandomAccessIterator>::value_type>)
457 : : __glibcxx_requires_valid_range(__first, __last);
458 : : __glibcxx_requires_heap(__first, __last);
459 : :
460 : : while (__last - __first > 1)
461 : : std::pop_heap(__first, _RandomAccessIterator(__last--));
462 : : }
463 : :
464 : : /**
465 : : * @brief Sort a heap using comparison functor.
466 : : * @param first Start of heap.
467 : : * @param last End of heap.
468 : : * @param comp Comparison functor to use.
469 : : * @ingroup heap
470 : : *
471 : : * This operation sorts the valid heap in the range [first,last).
472 : : * Comparisons are made using comp.
473 : : */
474 : : template<typename _RandomAccessIterator, typename _Compare>
475 : : void
476 : : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
477 : : _Compare __comp)
478 : : {
479 : : // concept requirements
480 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
481 : : _RandomAccessIterator>)
482 : : __glibcxx_requires_valid_range(__first, __last);
483 : : __glibcxx_requires_heap_pred(__first, __last, __comp);
484 : :
485 [ # # ]: 0 : while (__last - __first > 1)
486 : 0 : std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
487 : : }
488 : :
489 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
490 : : /**
491 : : * @brief Search the end of a heap.
492 : : * @param first Start of range.
493 : : * @param last End of range.
494 : : * @return An iterator pointing to the first element not in the heap.
495 : : * @ingroup heap
496 : : *
497 : : * This operation returns the last iterator i in [first, last) for which
498 : : * the range [first, i) is a heap.
499 : : */
500 : : template<typename _RandomAccessIterator>
501 : : inline _RandomAccessIterator
502 : : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
503 : : {
504 : : // concept requirements
505 : : __glibcxx_function_requires(_RandomAccessIteratorConcept<
506 : : _RandomAccessIterator>)
507 : : __glibcxx_function_requires(_LessThanComparableConcept<
508 : : typename iterator_traits<_RandomAccessIterator>::value_type>)
509 : : __glibcxx_requires_valid_range(__first, __last);
510 : :
511 : : return __first + std::__is_heap_until(__first, std::distance(__first,
512 : : __last));
513 : : }
514 : :
515 : : /**
516 : : * @brief Search the end of a heap using comparison functor.
517 : : * @param first Start of range.
518 : : * @param last End of range.
519 : : * @param comp Comparison functor to use.
520 : : * @return An iterator pointing to the first element not in the heap.
521 : : * @ingroup heap
522 : : *
523 : : * This operation returns the last iterator i in [first, last) for which
524 : : * the range [first, i) is a heap. Comparisons are made using comp.
525 : : */
526 : : template<typename _RandomAccessIterator, typename _Compare>
527 : : inline _RandomAccessIterator
528 : : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
529 : : _Compare __comp)
530 : : {
531 : : // concept requirements
532 : : __glibcxx_function_requires(_RandomAccessIteratorConcept<
533 : : _RandomAccessIterator>)
534 : : __glibcxx_requires_valid_range(__first, __last);
535 : :
536 : : return __first + std::__is_heap_until(__first, std::distance(__first,
537 : : __last),
538 : : __comp);
539 : : }
540 : :
541 : : /**
542 : : * @brief Determines whether a range is a heap.
543 : : * @param first Start of range.
544 : : * @param last End of range.
545 : : * @return True if range is a heap, false otherwise.
546 : : * @ingroup heap
547 : : */
548 : : template<typename _RandomAccessIterator>
549 : : inline bool
550 : : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
551 : : { return std::is_heap_until(__first, __last) == __last; }
552 : :
553 : : /**
554 : : * @brief Determines whether a range is a heap using comparison functor.
555 : : * @param first Start of range.
556 : : * @param last End of range.
557 : : * @param comp Comparison functor to use.
558 : : * @return True if range is a heap, false otherwise.
559 : : * @ingroup heap
560 : : */
561 : : template<typename _RandomAccessIterator, typename _Compare>
562 : : inline bool
563 : : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
564 : : _Compare __comp)
565 : : { return std::is_heap_until(__first, __last, __comp) == __last; }
566 : : #endif
567 : :
568 : : _GLIBCXX_END_NAMESPACE
569 : :
570 : : #endif /* _STL_HEAP_H */
|
