1 // Heap implementation -*- C++ -*-
2
3 // Copyright (C) 2001-2023 Free Software Foundation, Inc.
4 //
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)
9 // any later version.
10
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.
15
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.
19
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/>.
24
25 /*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
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.
37 *
38 * Copyright (c) 1997
39 * Silicon Graphics Computer Systems, Inc.
40 *
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.
48 */
49
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}
53 */
54
55 #ifndef _STL_HEAP_H
56 #define _STL_HEAP_H 1
57
58 #include <debug/debug.h>
59 #include <bits/move.h>
60 #include <bits/predefined_ops.h>
61 #include <bits/stl_iterator_base_funcs.h>
62
63 namespace std _GLIBCXX_VISIBILITY(default)
64 {
65 _GLIBCXX_BEGIN_NAMESPACE_VERSION
66
67 /**
68 * @defgroup heap_algorithms Heap
69 * @ingroup sorting_algorithms
70 */
71
72 template<typename _RandomAccessIterator, typename _Distance,
73 typename _Compare>
74 _GLIBCXX20_CONSTEXPR
75 _Distance
76 __is_heap_until(_RandomAccessIterator __first, _Distance __n,
77 _Compare& __comp)
78 {
79 _Distance __parent = 0;
80 for (_Distance __child = 1; __child < __n; ++__child)
81 {
82 if (__comp(__first + __parent, __first + __child))
83 return __child;
84 if ((__child & 1) == 0)
85 ++__parent;
86 }
87 return __n;
88 }
89
90 // __is_heap, a predicate testing whether or not a range is a heap.
91 // This function is an extension, not part of the C++ standard.
92 template<typename _RandomAccessIterator, typename _Distance>
93 _GLIBCXX20_CONSTEXPR
94 inline bool
95 __is_heap(_RandomAccessIterator __first, _Distance __n)
96 {
97 __gnu_cxx::__ops::_Iter_less_iter __comp;
98 return std::__is_heap_until(__first, __n, __comp) == __n;
99 }
100
101 template<typename _RandomAccessIterator, typename _Compare,
102 typename _Distance>
103 _GLIBCXX20_CONSTEXPR
104 inline bool
105 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
106 {
107 typedef __decltype(__comp) _Cmp;
108 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
109 return std::__is_heap_until(__first, __n, __cmp) == __n;
110 }
111
112 template<typename _RandomAccessIterator>
113 _GLIBCXX20_CONSTEXPR
114 inline bool
115 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
116 { return std::__is_heap(__first, std::distance(__first, __last)); }
117
118 template<typename _RandomAccessIterator, typename _Compare>
119 _GLIBCXX20_CONSTEXPR
120 inline bool
121 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
122 _Compare __comp)
123 {
124 return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
125 std::distance(__first, __last));
126 }
127
128 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
129 // + is_heap and is_heap_until in C++0x.
130
131 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
132 typename _Compare>
133 _GLIBCXX20_CONSTEXPR
134 void
135 __push_heap(_RandomAccessIterator __first,
136 _Distance __holeIndex, _Distance __topIndex, _Tp __value,
137 _Compare& __comp)
138 {
139 _Distance __parent = (__holeIndex - 1) / 2;
140 while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
141 {
142 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
143 __holeIndex = __parent;
144 __parent = (__holeIndex - 1) / 2;
145 }
146 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
147 }
148
149 /**
150 * @brief Push an element onto a heap.
151 * @param __first Start of heap.
152 * @param __last End of heap + element.
153 * @ingroup heap_algorithms
154 *
155 * This operation pushes the element at last-1 onto the valid heap
156 * over the range [__first,__last-1). After completion,
157 * [__first,__last) is a valid heap.
158 */
159 template<typename _RandomAccessIterator>
160 _GLIBCXX20_CONSTEXPR
161 inline void
162 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
163 {
164 typedef typename iterator_traits<_RandomAccessIterator>::value_type
165 _ValueType;
166 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
167 _DistanceType;
168
169 // concept requirements
170 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
171 _RandomAccessIterator>)
172 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
173 __glibcxx_requires_valid_range(__first, __last);
174 __glibcxx_requires_irreflexive(__first, __last);
175 __glibcxx_requires_heap(__first, __last - 1);
176
177 __gnu_cxx::__ops::_Iter_less_val __comp;
178 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
179 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
180 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
181 }
182
183 /**
184 * @brief Push an element onto a heap using comparison functor.
185 * @param __first Start of heap.
186 * @param __last End of heap + element.
187 * @param __comp Comparison functor.
188 * @ingroup heap_algorithms
189 *
190 * This operation pushes the element at __last-1 onto the valid
191 * heap over the range [__first,__last-1). After completion,
192 * [__first,__last) is a valid heap. Compare operations are
193 * performed using comp.
194 */
195 template<typename _RandomAccessIterator, typename _Compare>
196 _GLIBCXX20_CONSTEXPR
197 inline void
198 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
199 _Compare __comp)
200 {
201 typedef typename iterator_traits<_RandomAccessIterator>::value_type
202 _ValueType;
203 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
204 _DistanceType;
205
206 // concept requirements
207 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
208 _RandomAccessIterator>)
209 __glibcxx_requires_valid_range(__first, __last);
210 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
211 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
212
213 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
214 __cmp(_GLIBCXX_MOVE(__comp));
215 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
216 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
217 _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
218 }
219
220 template<typename _RandomAccessIterator, typename _Distance,
221 typename _Tp, typename _Compare>
222 _GLIBCXX20_CONSTEXPR
223 void
224 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
225 _Distance __len, _Tp __value, _Compare __comp)
226 {
227 const _Distance __topIndex = __holeIndex;
228 _Distance __secondChild = __holeIndex;
229 while (__secondChild < (__len - 1) / 2)
230 {
231 __secondChild = 2 * (__secondChild + 1);
232 if (__comp(__first + __secondChild,
233 __first + (__secondChild - 1)))
234 __secondChild--;
235 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
236 __holeIndex = __secondChild;
237 }
238 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
239 {
240 __secondChild = 2 * (__secondChild + 1);
241 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
242 + (__secondChild - 1)));
243 __holeIndex = __secondChild - 1;
244 }
245 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
246 __cmp(_GLIBCXX_MOVE(__comp));
247 std::__push_heap(__first, __holeIndex, __topIndex,
248 _GLIBCXX_MOVE(__value), __cmp);
249 }
250
251 template<typename _RandomAccessIterator, typename _Compare>
252 _GLIBCXX20_CONSTEXPR
253 inline void
254 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
255 _RandomAccessIterator __result, _Compare& __comp)
256 {
257 typedef typename iterator_traits<_RandomAccessIterator>::value_type
258 _ValueType;
259 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
260 _DistanceType;
261
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), __comp);
267 }
268
269 /**
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
275 *
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
278 * heap.
279 */
280 template<typename _RandomAccessIterator>
281 _GLIBCXX20_CONSTEXPR
282 inline void
283 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
284 {
285 // concept requirements
286 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
287 _RandomAccessIterator>)
288 __glibcxx_function_requires(_LessThanComparableConcept<
289 typename iterator_traits<_RandomAccessIterator>::value_type>)
290 __glibcxx_requires_non_empty_range(__first, __last);
291 __glibcxx_requires_valid_range(__first, __last);
292 __glibcxx_requires_irreflexive(__first, __last);
293 __glibcxx_requires_heap(__first, __last);
294
295 if (__last - __first > 1)
296 {
297 --__last;
298 __gnu_cxx::__ops::_Iter_less_iter __comp;
299 std::__pop_heap(__first, __last, __last, __comp);
300 }
301 }
302
303 /**
304 * @brief Pop an element off a heap using comparison functor.
305 * @param __first Start of heap.
306 * @param __last End of heap.
307 * @param __comp Comparison functor to use.
308 * @ingroup heap_algorithms
309 *
310 * This operation pops the top of the heap. The elements __first
311 * and __last-1 are swapped and [__first,__last-1) is made into a
312 * heap. Comparisons are made using comp.
313 */
314 template<typename _RandomAccessIterator, typename _Compare>
315 _GLIBCXX20_CONSTEXPR
316 inline void
317 pop_heap(_RandomAccessIterator __first,
318 _RandomAccessIterator __last, _Compare __comp)
319 {
320 // concept requirements
321 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
322 _RandomAccessIterator>)
323 __glibcxx_requires_valid_range(__first, __last);
324 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
325 __glibcxx_requires_non_empty_range(__first, __last);
326 __glibcxx_requires_heap_pred(__first, __last, __comp);
327
328 if (__last - __first > 1)
329 {
330 typedef __decltype(__comp) _Cmp;
331 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
332 --__last;
333 std::__pop_heap(__first, __last, __last, __cmp);
334 }
335 }
336
337 template<typename _RandomAccessIterator, typename _Compare>
338 _GLIBCXX20_CONSTEXPR
339 void
340 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
341 _Compare& __comp)
342 {
343 typedef typename iterator_traits<_RandomAccessIterator>::value_type
344 _ValueType;
345 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
346 _DistanceType;
347
348 if (__last - __first < 2)
349 return;
350
351 const _DistanceType __len = __last - __first;
352 _DistanceType __parent = (__len - 2) / 2;
353 while (true)
354 {
355 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
356 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
357 __comp);
358 if (__parent == 0)
359 return;
360 __parent--;
361 }
362 }
363
364 /**
365 * @brief Construct a heap over a range.
366 * @param __first Start of heap.
367 * @param __last End of heap.
368 * @ingroup heap_algorithms
369 *
370 * This operation makes the elements in [__first,__last) into a heap.
371 */
372 template<typename _RandomAccessIterator>
373 _GLIBCXX20_CONSTEXPR
374 inline void
375 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
376 {
377 // concept requirements
378 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
379 _RandomAccessIterator>)
380 __glibcxx_function_requires(_LessThanComparableConcept<
381 typename iterator_traits<_RandomAccessIterator>::value_type>)
382 __glibcxx_requires_valid_range(__first, __last);
383 __glibcxx_requires_irreflexive(__first, __last);
384
385 __gnu_cxx::__ops::_Iter_less_iter __comp;
386 std::__make_heap(__first, __last, __comp);
387 }
388
389 /**
390 * @brief Construct a heap over a range using comparison functor.
391 * @param __first Start of heap.
392 * @param __last End of heap.
393 * @param __comp Comparison functor to use.
394 * @ingroup heap_algorithms
395 *
396 * This operation makes the elements in [__first,__last) into a heap.
397 * Comparisons are made using __comp.
398 */
399 template<typename _RandomAccessIterator, typename _Compare>
400 _GLIBCXX20_CONSTEXPR
401 inline void
402 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
403 _Compare __comp)
404 {
405 // concept requirements
406 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
407 _RandomAccessIterator>)
408 __glibcxx_requires_valid_range(__first, __last);
409 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
410
411 typedef __decltype(__comp) _Cmp;
412 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
413 std::__make_heap(__first, __last, __cmp);
414 }
415
416 template<typename _RandomAccessIterator, typename _Compare>
417 _GLIBCXX20_CONSTEXPR
418 void
419 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
420 _Compare& __comp)
421 {
422 while (__last - __first > 1)
423 {
424 --__last;
425 std::__pop_heap(__first, __last, __last, __comp);
426 }
427 }
428
429 /**
430 * @brief Sort a heap.
431 * @param __first Start of heap.
432 * @param __last End of heap.
433 * @ingroup heap_algorithms
434 *
435 * This operation sorts the valid heap in the range [__first,__last).
436 */
437 template<typename _RandomAccessIterator>
438 _GLIBCXX20_CONSTEXPR
439 inline void
440 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
441 {
442 // concept requirements
443 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
444 _RandomAccessIterator>)
445 __glibcxx_function_requires(_LessThanComparableConcept<
446 typename iterator_traits<_RandomAccessIterator>::value_type>)
447 __glibcxx_requires_valid_range(__first, __last);
448 __glibcxx_requires_irreflexive(__first, __last);
449 __glibcxx_requires_heap(__first, __last);
450
451 __gnu_cxx::__ops::_Iter_less_iter __comp;
452 std::__sort_heap(__first, __last, __comp);
453 }
454
455 /**
456 * @brief Sort a heap using comparison functor.
457 * @param __first Start of heap.
458 * @param __last End of heap.
459 * @param __comp Comparison functor to use.
460 * @ingroup heap_algorithms
461 *
462 * This operation sorts the valid heap in the range [__first,__last).
463 * Comparisons are made using __comp.
464 */
465 template<typename _RandomAccessIterator, typename _Compare>
466 _GLIBCXX20_CONSTEXPR
467 inline void
468 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
469 _Compare __comp)
470 {
471 // concept requirements
472 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
473 _RandomAccessIterator>)
474 __glibcxx_requires_valid_range(__first, __last);
475 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
476 __glibcxx_requires_heap_pred(__first, __last, __comp);
477
478 typedef __decltype(__comp) _Cmp;
479 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
480 std::__sort_heap(__first, __last, __cmp);
481 }
482
483 #if __cplusplus >= 201103L
484 /**
485 * @brief Search the end of a heap.
486 * @param __first Start of range.
487 * @param __last End of range.
488 * @return An iterator pointing to the first element not in the heap.
489 * @ingroup heap_algorithms
490 *
491 * This operation returns the last iterator i in [__first, __last) for which
492 * the range [__first, i) is a heap.
493 */
494 template<typename _RandomAccessIterator>
495 _GLIBCXX20_CONSTEXPR
496 inline _RandomAccessIterator
497 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
498 {
499 // concept requirements
500 __glibcxx_function_requires(_RandomAccessIteratorConcept<
501 _RandomAccessIterator>)
502 __glibcxx_function_requires(_LessThanComparableConcept<
503 typename iterator_traits<_RandomAccessIterator>::value_type>)
504 __glibcxx_requires_valid_range(__first, __last);
505 __glibcxx_requires_irreflexive(__first, __last);
506
507 __gnu_cxx::__ops::_Iter_less_iter __comp;
508 return __first +
509 std::__is_heap_until(__first, std::distance(__first, __last), __comp);
510 }
511
512 /**
513 * @brief Search the end of a heap using comparison functor.
514 * @param __first Start of range.
515 * @param __last End of range.
516 * @param __comp Comparison functor to use.
517 * @return An iterator pointing to the first element not in the heap.
518 * @ingroup heap_algorithms
519 *
520 * This operation returns the last iterator i in [__first, __last) for which
521 * the range [__first, i) is a heap. Comparisons are made using __comp.
522 */
523 template<typename _RandomAccessIterator, typename _Compare>
524 _GLIBCXX20_CONSTEXPR
525 inline _RandomAccessIterator
526 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
527 _Compare __comp)
528 {
529 // concept requirements
530 __glibcxx_function_requires(_RandomAccessIteratorConcept<
531 _RandomAccessIterator>)
532 __glibcxx_requires_valid_range(__first, __last);
533 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
534
535 typedef __decltype(__comp) _Cmp;
536 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
537 return __first
538 + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
539 }
540
541 /**
542 * @brief Determines whether a range is a heap.
543 * @param __first Start of range.
544 * @param __last End of range.
545 * @return True if range is a heap, false otherwise.
546 * @ingroup heap_algorithms
547 */
548 template<typename _RandomAccessIterator>
549 _GLIBCXX20_CONSTEXPR
550 inline bool
551 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
552 { return std::is_heap_until(__first, __last) == __last; }
553
554 /**
555 * @brief Determines whether a range is a heap using comparison functor.
556 * @param __first Start of range.
557 * @param __last End of range.
558 * @param __comp Comparison functor to use.
559 * @return True if range is a heap, false otherwise.
560 * @ingroup heap_algorithms
561 */
562 template<typename _RandomAccessIterator, typename _Compare>
563 _GLIBCXX20_CONSTEXPR
564 inline bool
565 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
566 _Compare __comp)
567 {
568 // concept requirements
569 __glibcxx_function_requires(_RandomAccessIteratorConcept<
570 _RandomAccessIterator>)
571 __glibcxx_requires_valid_range(__first, __last);
572 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
573
574 const auto __dist = std::distance(__first, __last);
575 typedef __decltype(__comp) _Cmp;
576 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
577 return std::__is_heap_until(__first, __dist, __cmp) == __dist;
578 }
579 #endif
580
581 _GLIBCXX_END_NAMESPACE_VERSION
582 } // namespace
583
584 #endif /* _STL_HEAP_H */