libstdc++
stl_heap.h
Go to the documentation of this file.
1 // Heap implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2020 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  _GLIBCXX20_CONSTEXPR
74  _Distance
75  __is_heap_until(_RandomAccessIterator __first, _Distance __n,
76  _Compare& __comp)
77  {
78  _Distance __parent = 0;
79  for (_Distance __child = 1; __child < __n; ++__child)
80  {
81  if (__comp(__first + __parent, __first + __child))
82  return __child;
83  if ((__child & 1) == 0)
84  ++__parent;
85  }
86  return __n;
87  }
88 
89  // __is_heap, a predicate testing whether or not a range is a heap.
90  // This function is an extension, not part of the C++ standard.
91  template<typename _RandomAccessIterator, typename _Distance>
92  _GLIBCXX20_CONSTEXPR
93  inline bool
94  __is_heap(_RandomAccessIterator __first, _Distance __n)
95  {
96  __gnu_cxx::__ops::_Iter_less_iter __comp;
97  return std::__is_heap_until(__first, __n, __comp) == __n;
98  }
99 
100  template<typename _RandomAccessIterator, typename _Compare,
101  typename _Distance>
102  _GLIBCXX20_CONSTEXPR
103  inline bool
104  __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
105  {
106  typedef __decltype(__comp) _Cmp;
107  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
108  return std::__is_heap_until(__first, __n, __cmp) == __n;
109  }
110 
111  template<typename _RandomAccessIterator>
112  _GLIBCXX20_CONSTEXPR
113  inline bool
114  __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
115  { return std::__is_heap(__first, std::distance(__first, __last)); }
116 
117  template<typename _RandomAccessIterator, typename _Compare>
118  _GLIBCXX20_CONSTEXPR
119  inline bool
120  __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
121  _Compare __comp)
122  {
123  return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
124  std::distance(__first, __last));
125  }
126 
127  // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
128  // + is_heap and is_heap_until in C++0x.
129 
130  template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
131  typename _Compare>
132  _GLIBCXX20_CONSTEXPR
133  void
134  __push_heap(_RandomAccessIterator __first,
135  _Distance __holeIndex, _Distance __topIndex, _Tp __value,
136  _Compare& __comp)
137  {
138  _Distance __parent = (__holeIndex - 1) / 2;
139  while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
140  {
141  *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
142  __holeIndex = __parent;
143  __parent = (__holeIndex - 1) / 2;
144  }
145  *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
146  }
147 
148  /**
149  * @brief Push an element onto a heap.
150  * @param __first Start of heap.
151  * @param __last End of heap + element.
152  * @ingroup heap_algorithms
153  *
154  * This operation pushes the element at last-1 onto the valid heap
155  * over the range [__first,__last-1). After completion,
156  * [__first,__last) is a valid heap.
157  */
158  template<typename _RandomAccessIterator>
159  _GLIBCXX20_CONSTEXPR
160  inline void
161  push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
162  {
163  typedef typename iterator_traits<_RandomAccessIterator>::value_type
164  _ValueType;
165  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
166  _DistanceType;
167 
168  // concept requirements
169  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
170  _RandomAccessIterator>)
171  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
172  __glibcxx_requires_valid_range(__first, __last);
173  __glibcxx_requires_irreflexive(__first, __last);
174  __glibcxx_requires_heap(__first, __last - 1);
175 
176  __gnu_cxx::__ops::_Iter_less_val __comp;
177  _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
178  std::__push_heap(__first, _DistanceType((__last - __first) - 1),
179  _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
180  }
181 
182  /**
183  * @brief Push an element onto a heap using comparison functor.
184  * @param __first Start of heap.
185  * @param __last End of heap + element.
186  * @param __comp Comparison functor.
187  * @ingroup heap_algorithms
188  *
189  * This operation pushes the element at __last-1 onto the valid
190  * heap over the range [__first,__last-1). After completion,
191  * [__first,__last) is a valid heap. Compare operations are
192  * performed using comp.
193  */
194  template<typename _RandomAccessIterator, typename _Compare>
195  _GLIBCXX20_CONSTEXPR
196  inline void
197  push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
198  _Compare __comp)
199  {
200  typedef typename iterator_traits<_RandomAccessIterator>::value_type
201  _ValueType;
202  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
203  _DistanceType;
204 
205  // concept requirements
206  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
207  _RandomAccessIterator>)
208  __glibcxx_requires_valid_range(__first, __last);
209  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
210  __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
211 
212  __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
213  __cmp(_GLIBCXX_MOVE(__comp));
214  _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
215  std::__push_heap(__first, _DistanceType((__last - __first) - 1),
216  _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
217  }
218 
219  template<typename _RandomAccessIterator, typename _Distance,
220  typename _Tp, typename _Compare>
221  _GLIBCXX20_CONSTEXPR
222  void
223  __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
224  _Distance __len, _Tp __value, _Compare __comp)
225  {
226  const _Distance __topIndex = __holeIndex;
227  _Distance __secondChild = __holeIndex;
228  while (__secondChild < (__len - 1) / 2)
229  {
230  __secondChild = 2 * (__secondChild + 1);
231  if (__comp(__first + __secondChild,
232  __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  __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
245  __cmp(_GLIBCXX_MOVE(__comp));
246  std::__push_heap(__first, __holeIndex, __topIndex,
247  _GLIBCXX_MOVE(__value), __cmp);
248  }
249 
250  template<typename _RandomAccessIterator, typename _Compare>
251  _GLIBCXX20_CONSTEXPR
252  inline void
253  __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
254  _RandomAccessIterator __result, _Compare& __comp)
255  {
256  typedef typename iterator_traits<_RandomAccessIterator>::value_type
257  _ValueType;
258  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
259  _DistanceType;
260 
261  _ValueType __value = _GLIBCXX_MOVE(*__result);
262  *__result = _GLIBCXX_MOVE(*__first);
263  std::__adjust_heap(__first, _DistanceType(0),
264  _DistanceType(__last - __first),
265  _GLIBCXX_MOVE(__value), __comp);
266  }
267 
268  /**
269  * @brief Pop an element off a heap.
270  * @param __first Start of heap.
271  * @param __last End of heap.
272  * @pre [__first, __last) is a valid, non-empty range.
273  * @ingroup heap_algorithms
274  *
275  * This operation pops the top of the heap. The elements __first
276  * and __last-1 are swapped and [__first,__last-1) is made into a
277  * heap.
278  */
279  template<typename _RandomAccessIterator>
280  _GLIBCXX20_CONSTEXPR
281  inline void
282  pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
283  {
284  // concept requirements
285  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
286  _RandomAccessIterator>)
287  __glibcxx_function_requires(_LessThanComparableConcept<
288  typename iterator_traits<_RandomAccessIterator>::value_type>)
289  __glibcxx_requires_non_empty_range(__first, __last);
290  __glibcxx_requires_valid_range(__first, __last);
291  __glibcxx_requires_irreflexive(__first, __last);
292  __glibcxx_requires_heap(__first, __last);
293 
294  if (__last - __first > 1)
295  {
296  --__last;
297  __gnu_cxx::__ops::_Iter_less_iter __comp;
298  std::__pop_heap(__first, __last, __last, __comp);
299  }
300  }
301 
302  /**
303  * @brief Pop an element off a heap using comparison functor.
304  * @param __first Start of heap.
305  * @param __last End of heap.
306  * @param __comp Comparison functor to use.
307  * @ingroup heap_algorithms
308  *
309  * This operation pops the top of the heap. The elements __first
310  * and __last-1 are swapped and [__first,__last-1) is made into a
311  * heap. Comparisons are made using comp.
312  */
313  template<typename _RandomAccessIterator, typename _Compare>
314  _GLIBCXX20_CONSTEXPR
315  inline void
316  pop_heap(_RandomAccessIterator __first,
317  _RandomAccessIterator __last, _Compare __comp)
318  {
319  // concept requirements
320  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
321  _RandomAccessIterator>)
322  __glibcxx_requires_valid_range(__first, __last);
323  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
324  __glibcxx_requires_non_empty_range(__first, __last);
325  __glibcxx_requires_heap_pred(__first, __last, __comp);
326 
327  if (__last - __first > 1)
328  {
329  typedef __decltype(__comp) _Cmp;
330  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
331  --__last;
332  std::__pop_heap(__first, __last, __last, __cmp);
333  }
334  }
335 
336  template<typename _RandomAccessIterator, typename _Compare>
337  _GLIBCXX20_CONSTEXPR
338  void
339  __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
340  _Compare& __comp)
341  {
342  typedef typename iterator_traits<_RandomAccessIterator>::value_type
343  _ValueType;
344  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
345  _DistanceType;
346 
347  if (__last - __first < 2)
348  return;
349 
350  const _DistanceType __len = __last - __first;
351  _DistanceType __parent = (__len - 2) / 2;
352  while (true)
353  {
354  _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
355  std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
356  __comp);
357  if (__parent == 0)
358  return;
359  __parent--;
360  }
361  }
362 
363  /**
364  * @brief Construct a heap over a range.
365  * @param __first Start of heap.
366  * @param __last End of heap.
367  * @ingroup heap_algorithms
368  *
369  * This operation makes the elements in [__first,__last) into a heap.
370  */
371  template<typename _RandomAccessIterator>
372  _GLIBCXX20_CONSTEXPR
373  inline void
374  make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
375  {
376  // concept requirements
377  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
378  _RandomAccessIterator>)
379  __glibcxx_function_requires(_LessThanComparableConcept<
380  typename iterator_traits<_RandomAccessIterator>::value_type>)
381  __glibcxx_requires_valid_range(__first, __last);
382  __glibcxx_requires_irreflexive(__first, __last);
383 
384  __gnu_cxx::__ops::_Iter_less_iter __comp;
385  std::__make_heap(__first, __last, __comp);
386  }
387 
388  /**
389  * @brief Construct a heap over a range using comparison functor.
390  * @param __first Start of heap.
391  * @param __last End of heap.
392  * @param __comp Comparison functor to use.
393  * @ingroup heap_algorithms
394  *
395  * This operation makes the elements in [__first,__last) into a heap.
396  * Comparisons are made using __comp.
397  */
398  template<typename _RandomAccessIterator, typename _Compare>
399  _GLIBCXX20_CONSTEXPR
400  inline void
401  make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
402  _Compare __comp)
403  {
404  // concept requirements
405  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
406  _RandomAccessIterator>)
407  __glibcxx_requires_valid_range(__first, __last);
408  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
409 
410  typedef __decltype(__comp) _Cmp;
411  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
412  std::__make_heap(__first, __last, __cmp);
413  }
414 
415  template<typename _RandomAccessIterator, typename _Compare>
416  _GLIBCXX20_CONSTEXPR
417  void
418  __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
419  _Compare& __comp)
420  {
421  while (__last - __first > 1)
422  {
423  --__last;
424  std::__pop_heap(__first, __last, __last, __comp);
425  }
426  }
427 
428  /**
429  * @brief Sort a heap.
430  * @param __first Start of heap.
431  * @param __last End of heap.
432  * @ingroup heap_algorithms
433  *
434  * This operation sorts the valid heap in the range [__first,__last).
435  */
436  template<typename _RandomAccessIterator>
437  _GLIBCXX20_CONSTEXPR
438  inline void
439  sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
440  {
441  // concept requirements
442  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
443  _RandomAccessIterator>)
444  __glibcxx_function_requires(_LessThanComparableConcept<
445  typename iterator_traits<_RandomAccessIterator>::value_type>)
446  __glibcxx_requires_valid_range(__first, __last);
447  __glibcxx_requires_irreflexive(__first, __last);
448  __glibcxx_requires_heap(__first, __last);
449 
450  __gnu_cxx::__ops::_Iter_less_iter __comp;
451  std::__sort_heap(__first, __last, __comp);
452  }
453 
454  /**
455  * @brief Sort a heap using comparison functor.
456  * @param __first Start of heap.
457  * @param __last End of heap.
458  * @param __comp Comparison functor to use.
459  * @ingroup heap_algorithms
460  *
461  * This operation sorts the valid heap in the range [__first,__last).
462  * Comparisons are made using __comp.
463  */
464  template<typename _RandomAccessIterator, typename _Compare>
465  _GLIBCXX20_CONSTEXPR
466  inline void
467  sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
468  _Compare __comp)
469  {
470  // concept requirements
471  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
472  _RandomAccessIterator>)
473  __glibcxx_requires_valid_range(__first, __last);
474  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
475  __glibcxx_requires_heap_pred(__first, __last, __comp);
476 
477  typedef __decltype(__comp) _Cmp;
478  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
479  std::__sort_heap(__first, __last, __cmp);
480  }
481 
482 #if __cplusplus >= 201103L
483  /**
484  * @brief Search the end of a heap.
485  * @param __first Start of range.
486  * @param __last End of range.
487  * @return An iterator pointing to the first element not in the heap.
488  * @ingroup heap_algorithms
489  *
490  * This operation returns the last iterator i in [__first, __last) for which
491  * the range [__first, i) is a heap.
492  */
493  template<typename _RandomAccessIterator>
494  _GLIBCXX20_CONSTEXPR
495  inline _RandomAccessIterator
496  is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
497  {
498  // concept requirements
499  __glibcxx_function_requires(_RandomAccessIteratorConcept<
500  _RandomAccessIterator>)
501  __glibcxx_function_requires(_LessThanComparableConcept<
502  typename iterator_traits<_RandomAccessIterator>::value_type>)
503  __glibcxx_requires_valid_range(__first, __last);
504  __glibcxx_requires_irreflexive(__first, __last);
505 
506  __gnu_cxx::__ops::_Iter_less_iter __comp;
507  return __first +
508  std::__is_heap_until(__first, std::distance(__first, __last), __comp);
509  }
510 
511  /**
512  * @brief Search the end of a heap using comparison functor.
513  * @param __first Start of range.
514  * @param __last End of range.
515  * @param __comp Comparison functor to use.
516  * @return An iterator pointing to the first element not in the heap.
517  * @ingroup heap_algorithms
518  *
519  * This operation returns the last iterator i in [__first, __last) for which
520  * the range [__first, i) is a heap. Comparisons are made using __comp.
521  */
522  template<typename _RandomAccessIterator, typename _Compare>
523  _GLIBCXX20_CONSTEXPR
524  inline _RandomAccessIterator
525  is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
526  _Compare __comp)
527  {
528  // concept requirements
529  __glibcxx_function_requires(_RandomAccessIteratorConcept<
530  _RandomAccessIterator>)
531  __glibcxx_requires_valid_range(__first, __last);
532  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
533 
534  typedef __decltype(__comp) _Cmp;
535  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
536  return __first
537  + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
538  }
539 
540  /**
541  * @brief Determines whether a range is a heap.
542  * @param __first Start of range.
543  * @param __last End of range.
544  * @return True if range is a heap, false otherwise.
545  * @ingroup heap_algorithms
546  */
547  template<typename _RandomAccessIterator>
548  _GLIBCXX20_CONSTEXPR
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_algorithms
560  */
561  template<typename _RandomAccessIterator, typename _Compare>
562  _GLIBCXX20_CONSTEXPR
563  inline bool
564  is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
565  _Compare __comp)
566  {
567  // concept requirements
568  __glibcxx_function_requires(_RandomAccessIteratorConcept<
569  _RandomAccessIterator>)
570  __glibcxx_requires_valid_range(__first, __last);
571  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
572 
573  const auto __dist = std::distance(__first, __last);
574  typedef __decltype(__comp) _Cmp;
575  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
576  return std::__is_heap_until(__first, __dist, __cmp) == __dist;
577  }
578 #endif
579 
580 _GLIBCXX_END_NAMESPACE_VERSION
581 } // namespace
582 
583 #endif /* _STL_HEAP_H */
std
ISO C++ entities toplevel namespace is std.
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:178