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