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