1 // Heap implementation -*- C++ -*-
3 // Copyright (C) 2001-2014 Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Hewlett-Packard Company
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.
39 * Silicon Graphics Computer Systems, Inc.
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.
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}
58 #include <debug/debug.h>
59 #include <bits/move.h>
60 #include <bits/predefined_ops.h>
62 namespace std
_GLIBCXX_VISIBILITY(default)
64 _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 * @defgroup heap_algorithms Heap
68 * @ingroup sorting_algorithms
71 template<typename _RandomAccessIterator
, typename _Distance
,
74 __is_heap_until(_RandomAccessIterator __first
, _Distance __n
,
77 _Distance __parent
= 0;
78 for (_Distance __child
= 1; __child
< __n
; ++__child
)
80 if (__comp(__first
+ __parent
, __first
+ __child
))
82 if ((__child
& 1) == 0)
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
>
92 __is_heap(_RandomAccessIterator __first
, _Distance __n
)
94 return std::__is_heap_until(__first
, __n
,
95 __gnu_cxx::__ops::__iter_less_iter()) == __n
;
98 template<typename _RandomAccessIterator
, typename _Compare
,
101 __is_heap(_RandomAccessIterator __first
, _Compare __comp
, _Distance __n
)
103 return std::__is_heap_until(__first
, __n
,
104 __gnu_cxx::__ops::__iter_comp_iter(__comp
)) == __n
;
107 template<typename _RandomAccessIterator
>
109 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
110 { return std::__is_heap(__first
, std::distance(__first
, __last
)); }
112 template<typename _RandomAccessIterator
, typename _Compare
>
114 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
116 { return std::__is_heap(__first
, __comp
, std::distance(__first
, __last
)); }
118 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
119 // + is_heap and is_heap_until in C++0x.
121 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
,
124 __push_heap(_RandomAccessIterator __first
,
125 _Distance __holeIndex
, _Distance __topIndex
, _Tp __value
,
128 _Distance __parent
= (__holeIndex
- 1) / 2;
129 while (__holeIndex
> __topIndex
&& __comp(__first
+ __parent
, __value
))
131 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __parent
));
132 __holeIndex
= __parent
;
133 __parent
= (__holeIndex
- 1) / 2;
135 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(__value
);
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
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.
148 template<typename _RandomAccessIterator
>
150 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
152 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
154 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
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);
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());
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
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.
182 template<typename _RandomAccessIterator
, typename _Compare
>
184 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
187 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
189 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
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
);
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
));
204 template<typename _RandomAccessIterator
, typename _Distance
,
205 typename _Tp
, typename _Compare
>
207 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
208 _Distance __len
, _Tp __value
, _Compare __comp
)
210 const _Distance __topIndex
= __holeIndex
;
211 _Distance __secondChild
= __holeIndex
;
212 while (__secondChild
< (__len
- 1) / 2)
214 __secondChild
= 2 * (__secondChild
+ 1);
215 if (__comp(__first
+ __secondChild
,
216 __first
+ (__secondChild
- 1)))
218 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
219 __holeIndex
= __secondChild
;
221 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
223 __secondChild
= 2 * (__secondChild
+ 1);
224 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
225 + (__secondChild
- 1)));
226 __holeIndex
= __secondChild
- 1;
228 std::__push_heap(__first
, __holeIndex
, __topIndex
,
229 _GLIBCXX_MOVE(__value
),
230 __gnu_cxx::__ops::__iter_comp_val(__comp
));
233 template<typename _RandomAccessIterator
, typename _Compare
>
235 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
236 _RandomAccessIterator __result
, _Compare __comp
)
238 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
240 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
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
);
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
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
261 template<typename _RandomAccessIterator
>
263 pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
265 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
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
);
276 if (__last
- __first
> 1)
279 std::__pop_heap(__first
, __last
, __last
,
280 __gnu_cxx::__ops::__iter_less_iter());
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
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.
295 template<typename _RandomAccessIterator
, typename _Compare
>
297 pop_heap(_RandomAccessIterator __first
,
298 _RandomAccessIterator __last
, _Compare __comp
)
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
);
307 if (__last
- __first
> 1)
310 std::__pop_heap(__first
, __last
, __last
,
311 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
315 template<typename _RandomAccessIterator
, typename _Compare
>
317 __make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
320 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
322 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
325 if (__last
- __first
< 2)
328 const _DistanceType __len
= __last
- __first
;
329 _DistanceType __parent
= (__len
- 2) / 2;
332 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
333 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
),
342 * @brief Construct a heap over a range.
343 * @param __first Start of heap.
344 * @param __last End of heap.
345 * @ingroup heap_algorithms
347 * This operation makes the elements in [__first,__last) into a heap.
349 template<typename _RandomAccessIterator
>
351 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
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
);
360 std::__make_heap(__first
, __last
,
361 __gnu_cxx::__ops::__iter_less_iter());
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
371 * This operation makes the elements in [__first,__last) into a heap.
372 * Comparisons are made using __comp.
374 template<typename _RandomAccessIterator
, typename _Compare
>
376 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
379 // concept requirements
380 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
381 _RandomAccessIterator
>)
382 __glibcxx_requires_valid_range(__first
, __last
);
384 std::__make_heap(__first
, __last
,
385 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
388 template<typename _RandomAccessIterator
, typename _Compare
>
390 __sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
393 while (__last
- __first
> 1)
396 std::__pop_heap(__first
, __last
, __last
, __comp
);
401 * @brief Sort a heap.
402 * @param __first Start of heap.
403 * @param __last End of heap.
404 * @ingroup heap_algorithms
406 * This operation sorts the valid heap in the range [__first,__last).
408 template<typename _RandomAccessIterator
>
410 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
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
);
420 std::__sort_heap(__first
, __last
,
421 __gnu_cxx::__ops::__iter_less_iter());
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
431 * This operation sorts the valid heap in the range [__first,__last).
432 * Comparisons are made using __comp.
434 template<typename _RandomAccessIterator
, typename _Compare
>
436 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
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
);
445 std::__sort_heap(__first
, __last
,
446 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
449 #if __cplusplus >= 201103L
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
457 * This operation returns the last iterator i in [__first, __last) for which
458 * the range [__first, i) is a heap.
460 template<typename _RandomAccessIterator
>
461 inline _RandomAccessIterator
462 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
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
);
472 std::__is_heap_until(__first
, std::distance(__first
, __last
),
473 __gnu_cxx::__ops::__iter_less_iter());
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
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.
487 template<typename _RandomAccessIterator
, typename _Compare
>
488 inline _RandomAccessIterator
489 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
492 // concept requirements
493 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
494 _RandomAccessIterator
>)
495 __glibcxx_requires_valid_range(__first
, __last
);
498 + std::__is_heap_until(__first
, std::distance(__first
, __last
),
499 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
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
509 template<typename _RandomAccessIterator
>
511 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
512 { return std::is_heap_until(__first
, __last
) == __last
; }
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
522 template<typename _RandomAccessIterator
, typename _Compare
>
524 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
526 { return std::is_heap_until(__first
, __last
, __comp
) == __last
; }
529 _GLIBCXX_END_NAMESPACE_VERSION
532 #endif /* _STL_HEAP_H */