Slexy.org is shutting down and stopped accepting new Pastes on May 4th, 2021.
Existing Pastes will stop being available on or after May 10th, 2021.
Author: Autorresfsd Language: cpp
Description: Beschreibungalsjhda Timestamp: 2013-05-18 12:59:21 +0000
View raw paste Reply
  1. #include <iterator>
  2.  
  3. template< typename Iterator >
  4. void adjust_heap( Iterator first
  5.                   , typename std::iterator_traits< Iterator >::difference_type current
  6.                   , typename std::iterator_traits< Iterator >::difference_type size
  7.                   , typename std::iterator_traits< Iterator >::value_type tmp )
  8. {
  9.     typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
  10.  
  11.     diff_t top = current, next = 2 * current + 2;
  12.  
  13.     for ( ; next < size; current = next, next = 2 * next + 2 )
  14.     {
  15.         if ( *(first + next) < *(first + next - 1) )
  16.             --next;
  17.         *(first + current) = *(first + next);
  18.     }
  19.  
  20.     if ( next == size )
  21.         *(first + current) = *(first + size - 1), current = size - 1;
  22.  
  23.     for ( next = (current - 1) / 2;
  24.           top < current && *(first + next) < tmp;
  25.           current = next, next = (current - 1) / 2 )
  26.     {
  27.         *(first + current) = *(first + next);
  28.     }
  29.     *(first + current) = tmp;
  30. }
  31.  
  32. template< typename Iterator >
  33. void pop_heap( Iterator first, Iterator last)
  34. {
  35.     typedef typename std::iterator_traits< Iterator >::value_type value_t;
  36.  
  37.     value_t tmp = *--last;
  38.     *last = *first;
  39.     adjust_heap( first, 0, last - first, tmp );
  40. }
  41.  
  42. template< typename Iterator >
  43. void heap_sort( Iterator first, Iterator last )
  44. {
  45.     typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
  46.     for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
  47.         adjust_heap( first, current, last - first, *(first + current) );
  48.  
  49.     while ( first < last )
  50.         pop_heap( first, last-- );
  51. }
  52. [Bearbeiten]
View raw paste Reply