1 // Heap implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // 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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
64 #include <debug/debug.h>
65 #include <bits/move.h>
67 _GLIBCXX_BEGIN_NAMESPACE(std
)
70 * @defgroup heap_algorithms Heap Algorithms
71 * @ingroup sorting_algorithms
74 template<typename _RandomAccessIterator
, typename _Distance
>
76 __is_heap_until(_RandomAccessIterator __first
, _Distance __n
)
78 _Distance __parent
= 0;
79 for (_Distance __child
= 1; __child
< __n
; ++__child
)
81 if (__first
[__parent
] < __first
[__child
])
83 if ((__child
& 1) == 0)
89 template<typename _RandomAccessIterator
, typename _Distance
,
92 __is_heap_until(_RandomAccessIterator __first
, _Distance __n
,
95 _Distance __parent
= 0;
96 for (_Distance __child
= 1; __child
< __n
; ++__child
)
98 if (__comp(__first
[__parent
], __first
[__child
]))
100 if ((__child
& 1) == 0)
106 // __is_heap, a predicate testing whether or not a range is a heap.
107 // This function is an extension, not part of the C++ standard.
108 template<typename _RandomAccessIterator
, typename _Distance
>
110 __is_heap(_RandomAccessIterator __first
, _Distance __n
)
111 { return std::__is_heap_until(__first
, __n
) == __n
; }
113 template<typename _RandomAccessIterator
, typename _Compare
,
116 __is_heap(_RandomAccessIterator __first
, _Compare __comp
, _Distance __n
)
117 { return std::__is_heap_until(__first
, __n
, __comp
) == __n
; }
119 template<typename _RandomAccessIterator
>
121 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
122 { return std::__is_heap(__first
, std::distance(__first
, __last
)); }
124 template<typename _RandomAccessIterator
, typename _Compare
>
126 __is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
128 { return std::__is_heap(__first
, __comp
, std::distance(__first
, __last
)); }
130 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
131 // + is_heap and is_heap_until in C++0x.
133 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
>
135 __push_heap(_RandomAccessIterator __first
,
136 _Distance __holeIndex
, _Distance __topIndex
, _Tp __value
)
138 _Distance __parent
= (__holeIndex
- 1) / 2;
139 while (__holeIndex
> __topIndex
&& *(__first
+ __parent
) < __value
)
141 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __parent
));
142 __holeIndex
= __parent
;
143 __parent
= (__holeIndex
- 1) / 2;
145 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(__value
);
149 * @brief Push an element onto a heap.
150 * @param first Start of heap.
151 * @param last End of heap + element.
152 * @ingroup heap_algorithms
154 * This operation pushes the element at last-1 onto the valid heap over the
155 * range [first,last-1). After completion, [first,last) is a valid heap.
157 template<typename _RandomAccessIterator
>
159 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
161 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
163 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
166 // concept requirements
167 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
168 _RandomAccessIterator
>)
169 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
170 __glibcxx_requires_valid_range(__first
, __last
);
171 __glibcxx_requires_heap(__first
, __last
- 1);
173 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
174 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
175 _DistanceType(0), _GLIBCXX_MOVE(__value
));
178 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
,
181 __push_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
182 _Distance __topIndex
, _Tp __value
, _Compare __comp
)
184 _Distance __parent
= (__holeIndex
- 1) / 2;
185 while (__holeIndex
> __topIndex
186 && __comp(*(__first
+ __parent
), __value
))
188 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __parent
));
189 __holeIndex
= __parent
;
190 __parent
= (__holeIndex
- 1) / 2;
192 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(__value
);
196 * @brief Push an element onto a heap using comparison functor.
197 * @param first Start of heap.
198 * @param last End of heap + element.
199 * @param comp Comparison functor.
200 * @ingroup heap_algorithms
202 * This operation pushes the element at last-1 onto the valid heap over the
203 * range [first,last-1). After completion, [first,last) is a valid heap.
204 * Compare operations are performed using comp.
206 template<typename _RandomAccessIterator
, typename _Compare
>
208 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
211 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
213 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
216 // concept requirements
217 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
218 _RandomAccessIterator
>)
219 __glibcxx_requires_valid_range(__first
, __last
);
220 __glibcxx_requires_heap_pred(__first
, __last
- 1, __comp
);
222 _ValueType __value
= _GLIBCXX_MOVE(*(__last
- 1));
223 std::__push_heap(__first
, _DistanceType((__last
- __first
) - 1),
224 _DistanceType(0), _GLIBCXX_MOVE(__value
), __comp
);
227 template<typename _RandomAccessIterator
, typename _Distance
, typename _Tp
>
229 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
230 _Distance __len
, _Tp __value
)
232 const _Distance __topIndex
= __holeIndex
;
233 _Distance __secondChild
= __holeIndex
;
234 while (__secondChild
< (__len
- 1) / 2)
236 __secondChild
= 2 * (__secondChild
+ 1);
237 if (*(__first
+ __secondChild
) < *(__first
+ (__secondChild
- 1)))
239 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
240 __holeIndex
= __secondChild
;
242 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
244 __secondChild
= 2 * (__secondChild
+ 1);
245 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
246 + (__secondChild
- 1)));
247 __holeIndex
= __secondChild
- 1;
249 std::__push_heap(__first
, __holeIndex
, __topIndex
,
250 _GLIBCXX_MOVE(__value
));
253 template<typename _RandomAccessIterator
>
255 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
256 _RandomAccessIterator __result
)
258 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
260 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
263 _ValueType __value
= _GLIBCXX_MOVE(*__result
);
264 *__result
= _GLIBCXX_MOVE(*__first
);
265 std::__adjust_heap(__first
, _DistanceType(0),
266 _DistanceType(__last
- __first
),
267 _GLIBCXX_MOVE(__value
));
271 * @brief Pop an element off a heap.
272 * @param first Start of heap.
273 * @param last End of heap.
274 * @ingroup heap_algorithms
276 * This operation pops the top of the heap. The elements first and last-1
277 * are swapped and [first,last-1) is made into a heap.
279 template<typename _RandomAccessIterator
>
281 pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
283 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
286 // concept requirements
287 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
288 _RandomAccessIterator
>)
289 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
290 __glibcxx_requires_valid_range(__first
, __last
);
291 __glibcxx_requires_heap(__first
, __last
);
294 std::__pop_heap(__first
, __last
, __last
);
297 template<typename _RandomAccessIterator
, typename _Distance
,
298 typename _Tp
, typename _Compare
>
300 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
301 _Distance __len
, _Tp __value
, _Compare __comp
)
303 const _Distance __topIndex
= __holeIndex
;
304 _Distance __secondChild
= __holeIndex
;
305 while (__secondChild
< (__len
- 1) / 2)
307 __secondChild
= 2 * (__secondChild
+ 1);
308 if (__comp(*(__first
+ __secondChild
),
309 *(__first
+ (__secondChild
- 1))))
311 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
+ __secondChild
));
312 __holeIndex
= __secondChild
;
314 if ((__len
& 1) == 0 && __secondChild
== (__len
- 2) / 2)
316 __secondChild
= 2 * (__secondChild
+ 1);
317 *(__first
+ __holeIndex
) = _GLIBCXX_MOVE(*(__first
318 + (__secondChild
- 1)));
319 __holeIndex
= __secondChild
- 1;
321 std::__push_heap(__first
, __holeIndex
, __topIndex
,
322 _GLIBCXX_MOVE(__value
), __comp
);
325 template<typename _RandomAccessIterator
, typename _Compare
>
327 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
328 _RandomAccessIterator __result
, _Compare __comp
)
330 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
332 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
335 _ValueType __value
= _GLIBCXX_MOVE(*__result
);
336 *__result
= _GLIBCXX_MOVE(*__first
);
337 std::__adjust_heap(__first
, _DistanceType(0),
338 _DistanceType(__last
- __first
),
339 _GLIBCXX_MOVE(__value
), __comp
);
343 * @brief Pop an element off a heap using comparison functor.
344 * @param first Start of heap.
345 * @param last End of heap.
346 * @param comp Comparison functor to use.
347 * @ingroup heap_algorithms
349 * This operation pops the top of the heap. The elements first and last-1
350 * are swapped and [first,last-1) is made into a heap. Comparisons are
353 template<typename _RandomAccessIterator
, typename _Compare
>
355 pop_heap(_RandomAccessIterator __first
,
356 _RandomAccessIterator __last
, _Compare __comp
)
358 // concept requirements
359 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
360 _RandomAccessIterator
>)
361 __glibcxx_requires_valid_range(__first
, __last
);
362 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
365 std::__pop_heap(__first
, __last
, __last
, __comp
);
369 * @brief Construct a heap over a range.
370 * @param first Start of heap.
371 * @param last End of heap.
372 * @ingroup heap_algorithms
374 * This operation makes the elements in [first,last) into a heap.
376 template<typename _RandomAccessIterator
>
378 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
380 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
382 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
385 // concept requirements
386 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
387 _RandomAccessIterator
>)
388 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
389 __glibcxx_requires_valid_range(__first
, __last
);
391 if (__last
- __first
< 2)
394 const _DistanceType __len
= __last
- __first
;
395 _DistanceType __parent
= (__len
- 2) / 2;
398 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
399 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
));
407 * @brief Construct a heap over a range using comparison functor.
408 * @param first Start of heap.
409 * @param last End of heap.
410 * @param comp Comparison functor to use.
411 * @ingroup heap_algorithms
413 * This operation makes the elements in [first,last) into a heap.
414 * Comparisons are made using comp.
416 template<typename _RandomAccessIterator
, typename _Compare
>
418 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
421 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
423 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
426 // concept requirements
427 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
428 _RandomAccessIterator
>)
429 __glibcxx_requires_valid_range(__first
, __last
);
431 if (__last
- __first
< 2)
434 const _DistanceType __len
= __last
- __first
;
435 _DistanceType __parent
= (__len
- 2) / 2;
438 _ValueType __value
= _GLIBCXX_MOVE(*(__first
+ __parent
));
439 std::__adjust_heap(__first
, __parent
, __len
, _GLIBCXX_MOVE(__value
),
448 * @brief Sort a heap.
449 * @param first Start of heap.
450 * @param last End of heap.
451 * @ingroup heap_algorithms
453 * This operation sorts the valid heap in the range [first,last).
455 template<typename _RandomAccessIterator
>
457 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
459 // concept requirements
460 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
461 _RandomAccessIterator
>)
462 __glibcxx_function_requires(_LessThanComparableConcept
<
463 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
464 __glibcxx_requires_valid_range(__first
, __last
);
465 __glibcxx_requires_heap(__first
, __last
);
467 while (__last
- __first
> 1)
470 std::__pop_heap(__first
, __last
, __last
);
475 * @brief Sort a heap using comparison functor.
476 * @param first Start of heap.
477 * @param last End of heap.
478 * @param comp Comparison functor to use.
479 * @ingroup heap_algorithms
481 * This operation sorts the valid heap in the range [first,last).
482 * Comparisons are made using comp.
484 template<typename _RandomAccessIterator
, typename _Compare
>
486 sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
489 // concept requirements
490 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
491 _RandomAccessIterator
>)
492 __glibcxx_requires_valid_range(__first
, __last
);
493 __glibcxx_requires_heap_pred(__first
, __last
, __comp
);
495 while (__last
- __first
> 1)
498 std::__pop_heap(__first
, __last
, __last
, __comp
);
502 #ifdef __GXX_EXPERIMENTAL_CXX0X__
504 * @brief Search the end of a heap.
505 * @param first Start of range.
506 * @param last End of range.
507 * @return An iterator pointing to the first element not in the heap.
508 * @ingroup heap_algorithms
510 * This operation returns the last iterator i in [first, last) for which
511 * the range [first, i) is a heap.
513 template<typename _RandomAccessIterator
>
514 inline _RandomAccessIterator
515 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
517 // concept requirements
518 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
519 _RandomAccessIterator
>)
520 __glibcxx_function_requires(_LessThanComparableConcept
<
521 typename iterator_traits
<_RandomAccessIterator
>::value_type
>)
522 __glibcxx_requires_valid_range(__first
, __last
);
524 return __first
+ std::__is_heap_until(__first
, std::distance(__first
,
529 * @brief Search the end of a heap using comparison functor.
530 * @param first Start of range.
531 * @param last End of range.
532 * @param comp Comparison functor to use.
533 * @return An iterator pointing to the first element not in the heap.
534 * @ingroup heap_algorithms
536 * This operation returns the last iterator i in [first, last) for which
537 * the range [first, i) is a heap. Comparisons are made using comp.
539 template<typename _RandomAccessIterator
, typename _Compare
>
540 inline _RandomAccessIterator
541 is_heap_until(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
544 // concept requirements
545 __glibcxx_function_requires(_RandomAccessIteratorConcept
<
546 _RandomAccessIterator
>)
547 __glibcxx_requires_valid_range(__first
, __last
);
549 return __first
+ std::__is_heap_until(__first
, std::distance(__first
,
555 * @brief Determines whether a range is a heap.
556 * @param first Start of range.
557 * @param last End of range.
558 * @return True if range is a heap, false otherwise.
559 * @ingroup heap_algorithms
561 template<typename _RandomAccessIterator
>
563 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
564 { return std::is_heap_until(__first
, __last
) == __last
; }
567 * @brief Determines whether a range is a heap using comparison functor.
568 * @param first Start of range.
569 * @param last End of range.
570 * @param comp Comparison functor to use.
571 * @return True if range is a heap, false otherwise.
572 * @ingroup heap_algorithms
574 template<typename _RandomAccessIterator
, typename _Compare
>
576 is_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
578 { return std::is_heap_until(__first
, __last
, __comp
) == __last
; }
581 _GLIBCXX_END_NAMESPACE
583 #endif /* _STL_HEAP_H */