1 // Heap implementation -*- C++ -*-
3 // Copyright (C) 2001-2016 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_irreflexive(__first
, __last
);
163 __glibcxx_requires_heap(__first
, __last
- 1);
165 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
166 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
167 _DistanceType(0), _GLIBCXX_MOVE(__value
),
168 __gnu_cxx::__ops::__iter_less_val());
172 * @brief Push an element onto a heap using comparison functor.
173 * @param __first Start of heap.
174 * @param __last End of heap + element.
175 * @param __comp Comparison functor.
176 * @ingroup heap_algorithms
178 * This operation pushes the element at __last-1 onto the valid
179 * heap over the range [__first,__last-1). After completion,
180 * [__first,__last) is a valid heap. Compare operations are
181 * performed using comp.
183 template<typename _RandomAccessIterator
, typename _Compare
>
185 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
188 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
190 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
193 // concept requirements
194 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
195 _RandomAccessIterator
>)
196 __glibcxx_requires_valid_range(__first
, __last
);
197 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
198 __glibcxx_requires_heap_pred(__first
, __last
- 1, __comp
);
200 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
201 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
202 _DistanceType(0), _GLIBCXX_MOVE(__value
),
203 __gnu_cxx::__ops::__iter_comp_val(__comp
));
206 template<typename _RandomAccessIterator
, typename _Distance
,
207 typename _Tp
, typename _Compare
>
209 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
210 _Distance __len
, _Tp __value
, _Compare __comp
)
212 const _Distance __topIndex
= __holeIndex
;
213 _Distance __secondChild
= __holeIndex
;
214 while (__secondChild
< (__len
- 1) / 2)
216 __secondChild
= 2 * (__secondChild
+ 1);
217 if (__comp(__first
+ __secondChild
,
218 __first
+ (__secondChild
- 1)))
220 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
221 __holeIndex
= __secondChild
;
223 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
225 __secondChild
= 2 * (__secondChild
+ 1);
226 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
227 + (__secondChild
- 1)));
228 __holeIndex
= __secondChild
- 1;
230 std::__push_heap(__first
, __holeIndex
, __topIndex
,
231 _GLIBCXX_MOVE(__value
),
232 __gnu_cxx::__ops::__iter_comp_val(__comp
));
235 template<typename _RandomAccessIterator
, typename _Compare
>
237 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
238 _RandomAccessIterator __result
, _Compare __comp
)
240 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
242 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
245 _ValueType __value
= _GLIBCXX_MOVE(*__result
);
246 *__result
= _GLIBCXX_MOVE(*__first
);
247 std::__adjust_heap(__first
, _DistanceType(0),
248 _DistanceType(__last
- __first
),
249 _GLIBCXX_MOVE(__value
), __comp
);
253 * @brief Pop an element off a heap.
254 * @param __first Start of heap.
255 * @param __last End of heap.
256 * @pre [__first, __last) is a valid, non-empty range.
257 * @ingroup heap_algorithms
259 * This operation pops the top of the heap. The elements __first
260 * and __last-1 are swapped and [__first,__last-1) is made into a
263 template<typename _RandomAccessIterator
>
265 pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
267 // concept requirements
268 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
269 _RandomAccessIterator
>)
270 __glibcxx_function_requires(_LessThanComparableConcept
<
271 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
272 __glibcxx_requires_non_empty_range(__first
, __last
);
273 __glibcxx_requires_valid_range(__first
, __last
);
274 __glibcxx_requires_irreflexive(__first
, __last
);
275 __glibcxx_requires_heap(__first
, __last
);
277 if (__last
- __first
> 1)
280 std::__pop_heap(__first
, __last
, __last
,
281 __gnu_cxx::__ops::__iter_less_iter());
286 * @brief Pop an element off a heap using comparison functor.
287 * @param __first Start of heap.
288 * @param __last End of heap.
289 * @param __comp Comparison functor to use.
290 * @ingroup heap_algorithms
292 * This operation pops the top of the heap. The elements __first
293 * and __last-1 are swapped and [__first,__last-1) is made into a
294 * heap. Comparisons are made using comp.
296 template<typename _RandomAccessIterator
, typename _Compare
>
298 pop_heap(_RandomAccessIterator __first
,
299 _RandomAccessIterator __last
, _Compare __comp
)
301 // concept requirements
302 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
303 _RandomAccessIterator
>)
304 __glibcxx_requires_valid_range(__first
, __last
);
305 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
306 __glibcxx_requires_non_empty_range(__first
, __last
);
307 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
309 if (__last
- __first
> 1)
312 std::__pop_heap(__first
, __last
, __last
,
313 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
317 template<typename _RandomAccessIterator
, typename _Compare
>
319 __make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
322 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
324 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
327 if (__last
- __first
< 2)
330 const _DistanceType __len
= __last
- __first
;
331 _DistanceType __parent
= (__len
- 2) / 2;
334 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
335 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
),
344 * @brief Construct a heap over a range.
345 * @param __first Start of heap.
346 * @param __last End of heap.
347 * @ingroup heap_algorithms
349 * This operation makes the elements in [__first,__last) into a heap.
351 template<typename _RandomAccessIterator
>
353 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
355 // concept requirements
356 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
357 _RandomAccessIterator
>)
358 __glibcxx_function_requires(_LessThanComparableConcept
<
359 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
360 __glibcxx_requires_valid_range(__first
, __last
);
361 __glibcxx_requires_irreflexive(__first
, __last
);
363 std::__make_heap(__first
, __last
,
364 __gnu_cxx::__ops::__iter_less_iter());
368 * @brief Construct a heap over a range using comparison functor.
369 * @param __first Start of heap.
370 * @param __last End of heap.
371 * @param __comp Comparison functor to use.
372 * @ingroup heap_algorithms
374 * This operation makes the elements in [__first,__last) into a heap.
375 * Comparisons are made using __comp.
377 template<typename _RandomAccessIterator
, typename _Compare
>
379 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
382 // concept requirements
383 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
384 _RandomAccessIterator
>)
385 __glibcxx_requires_valid_range(__first
, __last
);
386 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
388 std::__make_heap(__first
, __last
,
389 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
392 template<typename _RandomAccessIterator
, typename _Compare
>
394 __sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
397 while (__last
- __first
> 1)
400 std::__pop_heap(__first
, __last
, __last
, __comp
);
405 * @brief Sort a heap.
406 * @param __first Start of heap.
407 * @param __last End of heap.
408 * @ingroup heap_algorithms
410 * This operation sorts the valid heap in the range [__first,__last).
412 template<typename _RandomAccessIterator
>
414 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
416 // concept requirements
417 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
418 _RandomAccessIterator
>)
419 __glibcxx_function_requires(_LessThanComparableConcept
<
420 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
421 __glibcxx_requires_valid_range(__first
, __last
);
422 __glibcxx_requires_irreflexive(__first
, __last
);
423 __glibcxx_requires_heap(__first
, __last
);
425 std::__sort_heap(__first
, __last
,
426 __gnu_cxx::__ops::__iter_less_iter());
430 * @brief Sort a heap using comparison functor.
431 * @param __first Start of heap.
432 * @param __last End of heap.
433 * @param __comp Comparison functor to use.
434 * @ingroup heap_algorithms
436 * This operation sorts the valid heap in the range [__first,__last).
437 * Comparisons are made using __comp.
439 template<typename _RandomAccessIterator
, typename _Compare
>
441 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
444 // concept requirements
445 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
446 _RandomAccessIterator
>)
447 __glibcxx_requires_valid_range(__first
, __last
);
448 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
449 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
451 std::__sort_heap(__first
, __last
,
452 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
455 #if __cplusplus >= 201103L
457 * @brief Search the end of a heap.
458 * @param __first Start of range.
459 * @param __last End of range.
460 * @return An iterator pointing to the first element not in the heap.
461 * @ingroup heap_algorithms
463 * This operation returns the last iterator i in [__first, __last) for which
464 * the range [__first, i) is a heap.
466 template<typename _RandomAccessIterator
>
467 inline _RandomAccessIterator
468 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
470 // concept requirements
471 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
472 _RandomAccessIterator
>)
473 __glibcxx_function_requires(_LessThanComparableConcept
<
474 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
475 __glibcxx_requires_valid_range(__first
, __last
);
476 __glibcxx_requires_irreflexive(__first
, __last
);
479 std::__is_heap_until(__first
, std::distance(__first
, __last
),
480 __gnu_cxx::__ops::__iter_less_iter());
484 * @brief Search the end of a heap using comparison functor.
485 * @param __first Start of range.
486 * @param __last End of range.
487 * @param __comp Comparison functor to use.
488 * @return An iterator pointing to the first element not in the heap.
489 * @ingroup heap_algorithms
491 * This operation returns the last iterator i in [__first, __last) for which
492 * the range [__first, i) is a heap. Comparisons are made using __comp.
494 template<typename _RandomAccessIterator
, typename _Compare
>
495 inline _RandomAccessIterator
496 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
499 // concept requirements
500 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
501 _RandomAccessIterator
>)
502 __glibcxx_requires_valid_range(__first
, __last
);
503 __glibcxx_requires_irreflexive_pred(__first
, __last
, __comp
);
506 + std::__is_heap_until(__first
, std::distance(__first
, __last
),
507 __gnu_cxx::__ops::__iter_comp_iter(__comp
));
511 * @brief Determines whether a range is a heap.
512 * @param __first Start of range.
513 * @param __last End of range.
514 * @return True if range is a heap, false otherwise.
515 * @ingroup heap_algorithms
517 template<typename _RandomAccessIterator
>
519 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
520 { return std::is_heap_until(__first
, __last
) == __last
; }
523 * @brief Determines whether a range is a heap using comparison functor.
524 * @param __first Start of range.
525 * @param __last End of range.
526 * @param __comp Comparison functor to use.
527 * @return True if range is a heap, false otherwise.
528 * @ingroup heap_algorithms
530 template<typename _RandomAccessIterator
, typename _Compare
>
532 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
534 { return std::is_heap_until(__first
, __last
, __comp
) == __last
; }
537 _GLIBCXX_END_NAMESPACE_VERSION
540 #endif /* _STL_HEAP_H */