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