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