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