libstdc++
stl_heap.h
Go to the documentation of this file.
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 */
std
ISO C++ entities toplevel namespace is std.
std::distance
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:138
std::is_heap_until
_RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Search the end of a heap using comparison functor.
Definition: stl_heap.h:505