1 // Heap implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
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)
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.
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.
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/>.
29 * Hewlett-Packard Company
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.
40 * Silicon Graphics Computer Systems, Inc.
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.
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}
59 #include <debug/debug.h>
60 #include <bits/move.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
>
73 __is_heap_until(_RandomAccessIterator __first
, _Distance __n
)
75 _Distance __parent
= 0;
76 for (_Distance __child
= 1; __child
< __n
; ++__child
)
78 if (__first
[__parent
] < __first
[__child
])
80 if ((__child
& 1) == 0)
86 template<typename _RandomAccessIterator
, typename _Distance
,
89 __is_heap_until(_RandomAccessIterator __first
, _Distance __n
,
92 _Distance __parent
= 0;
93 for (_Distance __child
= 1; __child
< __n
; ++__child
)
95 if (__comp(__first
[__parent
], __first
[__child
]))
97 if ((__child
& 1) == 0)
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
>
107 __is_heap(_RandomAccessIterator __first
, _Distance __n
)
108 { return std::__is_heap_until(__first
, __n
) == __n
; }
110 template<typename _RandomAccessIterator
, typename _Compare
,
113 __is_heap(_RandomAccessIterator __first
, _Compare __comp
, _Distance __n
)
114 { return std::__is_heap_until(__first
, __n
, __comp
) == __n
; }
116 template<typename _RandomAccessIterator
>
118 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
119 { return std::__is_heap(__first
, std::distance(__first
, __last
)); }
121 template<typename _RandomAccessIterator
, typename _Compare
>
123 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
125 { return std::__is_heap(__first
, __comp
, std::distance(__first
, __last
)); }
127 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
128 // + is_heap and is_heap_until in C++0x.
130 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
>
132 __push_heap(_RandomAccessIterator __first
,
133 _Distance __holeIndex
, _Distance __topIndex
, _Tp __value
)
135 _Distance __parent
= (__holeIndex
- 1) / 2;
136 while (__holeIndex
> __topIndex
&& *(__first
+ __parent
) < __value
)
138 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __parent
));
139 __holeIndex
= __parent
;
140 __parent
= (__holeIndex
- 1) / 2;
142 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(__value
);
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
151 * This operation pushes the element at last-1 onto the valid heap
152 * over the range [__first,__last-1). After completion,
153 * [__first,__last) is a valid heap.
155 template<typename _RandomAccessIterator
>
157 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
159 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
161 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
164 // concept requirements
165 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
166 _RandomAccessIterator
>)
167 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
168 __glibcxx_requires_valid_range(__first
, __last
);
169 __glibcxx_requires_heap(__first
, __last
- 1);
171 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
172 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
173 _DistanceType(0), _GLIBCXX_MOVE(__value
));
176 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
,
179 __push_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
180 _Distance __topIndex
, _Tp __value
, _Compare __comp
)
182 _Distance __parent
= (__holeIndex
- 1) / 2;
183 while (__holeIndex
> __topIndex
184 && __comp(*(__first
+ __parent
), __value
))
186 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __parent
));
187 __holeIndex
= __parent
;
188 __parent
= (__holeIndex
- 1) / 2;
190 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(__value
);
194 * @brief Push an element onto a heap using comparison functor.
195 * @param __first Start of heap.
196 * @param __last End of heap + element.
197 * @param __comp Comparison functor.
198 * @ingroup heap_algorithms
200 * This operation pushes the element at __last-1 onto the valid
201 * heap over the range [__first,__last-1). After completion,
202 * [__first,__last) is a valid heap. Compare operations are
203 * performed using comp.
205 template<typename _RandomAccessIterator
, typename _Compare
>
207 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
210 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
212 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
215 // concept requirements
216 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
217 _RandomAccessIterator
>)
218 __glibcxx_requires_valid_range(__first
, __last
);
219 __glibcxx_requires_heap_pred(__first
, __last
- 1, __comp
);
221 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
222 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
223 _DistanceType(0), _GLIBCXX_MOVE(__value
), __comp
);
226 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
>
228 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
229 _Distance __len
, _Tp __value
)
231 const _Distance __topIndex
= __holeIndex
;
232 _Distance __secondChild
= __holeIndex
;
233 while (__secondChild
< (__len
- 1) / 2)
235 __secondChild
= 2 * (__secondChild
+ 1);
236 if (*(__first
+ __secondChild
) < *(__first
+ (__secondChild
- 1)))
238 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
239 __holeIndex
= __secondChild
;
241 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
243 __secondChild
= 2 * (__secondChild
+ 1);
244 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
245 + (__secondChild
- 1)));
246 __holeIndex
= __secondChild
- 1;
248 std::__push_heap(__first
, __holeIndex
, __topIndex
,
249 _GLIBCXX_MOVE(__value
));
252 template<typename _RandomAccessIterator
>
254 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
255 _RandomAccessIterator __result
)
257 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
259 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
262 _ValueType __value
= _GLIBCXX_MOVE(*__result
);
263 *__result
= _GLIBCXX_MOVE(*__first
);
264 std::__adjust_heap(__first
, _DistanceType(0),
265 _DistanceType(__last
- __first
),
266 _GLIBCXX_MOVE(__value
));
270 * @brief Pop an element off a heap.
271 * @param __first Start of heap.
272 * @param __last End of heap.
273 * @pre [__first, __last) is a valid, non-empty range.
274 * @ingroup heap_algorithms
276 * This operation pops the top of the heap. The elements __first
277 * and __last-1 are swapped and [__first,__last-1) is made into a
280 template<typename _RandomAccessIterator
>
282 pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
284 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
287 // concept requirements
288 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
289 _RandomAccessIterator
>)
290 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
291 __glibcxx_requires_non_empty_range(__first
, __last
);
292 __glibcxx_requires_valid_range(__first
, __last
);
293 __glibcxx_requires_heap(__first
, __last
);
296 std::__pop_heap(__first
, __last
, __last
);
299 template<typename _RandomAccessIterator
, typename _Distance
,
300 typename _Tp
, typename _Compare
>
302 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
303 _Distance __len
, _Tp __value
, _Compare __comp
)
305 const _Distance __topIndex
= __holeIndex
;
306 _Distance __secondChild
= __holeIndex
;
307 while (__secondChild
< (__len
- 1) / 2)
309 __secondChild
= 2 * (__secondChild
+ 1);
310 if (__comp(*(__first
+ __secondChild
),
311 *(__first
+ (__secondChild
- 1))))
313 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
314 __holeIndex
= __secondChild
;
316 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
318 __secondChild
= 2 * (__secondChild
+ 1);
319 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
320 + (__secondChild
- 1)));
321 __holeIndex
= __secondChild
- 1;
323 std::__push_heap(__first
, __holeIndex
, __topIndex
,
324 _GLIBCXX_MOVE(__value
), __comp
);
327 template<typename _RandomAccessIterator
, typename _Compare
>
329 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
330 _RandomAccessIterator __result
, _Compare __comp
)
332 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
334 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
337 _ValueType __value
= _GLIBCXX_MOVE(*__result
);
338 *__result
= _GLIBCXX_MOVE(*__first
);
339 std::__adjust_heap(__first
, _DistanceType(0),
340 _DistanceType(__last
- __first
),
341 _GLIBCXX_MOVE(__value
), __comp
);
345 * @brief Pop an element off a heap using comparison functor.
346 * @param __first Start of heap.
347 * @param __last End of heap.
348 * @param __comp Comparison functor to use.
349 * @ingroup heap_algorithms
351 * This operation pops the top of the heap. The elements __first
352 * and __last-1 are swapped and [__first,__last-1) is made into a
353 * heap. Comparisons are made using comp.
355 template<typename _RandomAccessIterator
, typename _Compare
>
357 pop_heap(_RandomAccessIterator __first
,
358 _RandomAccessIterator __last
, _Compare __comp
)
360 // concept requirements
361 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
362 _RandomAccessIterator
>)
363 __glibcxx_requires_valid_range(__first
, __last
);
364 __glibcxx_requires_non_empty_range(__first
, __last
);
365 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
368 std::__pop_heap(__first
, __last
, __last
, __comp
);
372 * @brief Construct a heap over a range.
373 * @param __first Start of heap.
374 * @param __last End of heap.
375 * @ingroup heap_algorithms
377 * This operation makes the elements in [__first,__last) into a heap.
379 template<typename _RandomAccessIterator
>
381 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
383 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
385 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
388 // concept requirements
389 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
390 _RandomAccessIterator
>)
391 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
392 __glibcxx_requires_valid_range(__first
, __last
);
394 if (__last
- __first
< 2)
397 const _DistanceType __len
= __last
- __first
;
398 _DistanceType __parent
= (__len
- 2) / 2;
401 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
402 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
));
410 * @brief Construct a heap over a range using comparison functor.
411 * @param __first Start of heap.
412 * @param __last End of heap.
413 * @param __comp Comparison functor to use.
414 * @ingroup heap_algorithms
416 * This operation makes the elements in [__first,__last) into a heap.
417 * Comparisons are made using __comp.
419 template<typename _RandomAccessIterator
, typename _Compare
>
421 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
424 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
426 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
429 // concept requirements
430 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
431 _RandomAccessIterator
>)
432 __glibcxx_requires_valid_range(__first
, __last
);
434 if (__last
- __first
< 2)
437 const _DistanceType __len
= __last
- __first
;
438 _DistanceType __parent
= (__len
- 2) / 2;
441 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
442 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
),
451 * @brief Sort a heap.
452 * @param __first Start of heap.
453 * @param __last End of heap.
454 * @ingroup heap_algorithms
456 * This operation sorts the valid heap in the range [__first,__last).
458 template<typename _RandomAccessIterator
>
460 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
462 // concept requirements
463 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
464 _RandomAccessIterator
>)
465 __glibcxx_function_requires(_LessThanComparableConcept
<
466 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
467 __glibcxx_requires_valid_range(__first
, __last
);
468 __glibcxx_requires_heap(__first
, __last
);
470 while (__last
- __first
> 1)
473 std::__pop_heap(__first
, __last
, __last
);
478 * @brief Sort a heap using comparison functor.
479 * @param __first Start of heap.
480 * @param __last End of heap.
481 * @param __comp Comparison functor to use.
482 * @ingroup heap_algorithms
484 * This operation sorts the valid heap in the range [__first,__last).
485 * Comparisons are made using __comp.
487 template<typename _RandomAccessIterator
, typename _Compare
>
489 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
492 // concept requirements
493 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
494 _RandomAccessIterator
>)
495 __glibcxx_requires_valid_range(__first
, __last
);
496 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
498 while (__last
- __first
> 1)
501 std::__pop_heap(__first
, __last
, __last
, __comp
);
505 #ifdef __GXX_EXPERIMENTAL_CXX0X__
507 * @brief Search the end of a heap.
508 * @param __first Start of range.
509 * @param __last End of range.
510 * @return An iterator pointing to the first element not in the heap.
511 * @ingroup heap_algorithms
513 * This operation returns the last iterator i in [__first, __last) for which
514 * the range [__first, i) is a heap.
516 template<typename _RandomAccessIterator
>
517 inline _RandomAccessIterator
518 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
520 // concept requirements
521 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
522 _RandomAccessIterator
>)
523 __glibcxx_function_requires(_LessThanComparableConcept
<
524 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
525 __glibcxx_requires_valid_range(__first
, __last
);
527 return __first
+ std::__is_heap_until(__first
, std::distance(__first
,
532 * @brief Search the end of a heap using comparison functor.
533 * @param __first Start of range.
534 * @param __last End of range.
535 * @param __comp Comparison functor to use.
536 * @return An iterator pointing to the first element not in the heap.
537 * @ingroup heap_algorithms
539 * This operation returns the last iterator i in [__first, __last) for which
540 * the range [__first, i) is a heap. Comparisons are made using __comp.
542 template<typename _RandomAccessIterator
, typename _Compare
>
543 inline _RandomAccessIterator
544 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
547 // concept requirements
548 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
549 _RandomAccessIterator
>)
550 __glibcxx_requires_valid_range(__first
, __last
);
552 return __first
+ std::__is_heap_until(__first
, std::distance(__first
,
558 * @brief Determines whether a range is a heap.
559 * @param __first Start of range.
560 * @param __last End of range.
561 * @return True if range is a heap, false otherwise.
562 * @ingroup heap_algorithms
564 template<typename _RandomAccessIterator
>
566 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
567 { return std::is_heap_until(__first
, __last
) == __last
; }
570 * @brief Determines whether a range is a heap using comparison functor.
571 * @param __first Start of range.
572 * @param __last End of range.
573 * @param __comp Comparison functor to use.
574 * @return True if range is a heap, false otherwise.
575 * @ingroup heap_algorithms
577 template<typename _RandomAccessIterator
, typename _Compare
>
579 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
581 { return std::is_heap_until(__first
, __last
, __comp
) == __last
; }
584 _GLIBCXX_END_NAMESPACE_VERSION
587 #endif /* _STL_HEAP_H */