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