С++ для начинающих


         

Алгоритм sort_heap()


template< class RandomAccessIterator >

void

sort_heap( RandomAccessIterator first,

           RandomAccessIterator last );

template< class RandomAccessIterator, class Compare >

void

sort_heap( RandomAccessIterator first,

           RandomAccessIterator last, Compare comp );

sort_heap() сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.

#include <algorithm>

#include <vector>

#include <assert.h>

template <class Type>

void print_elements( Type elem ) { cout << elem << " "; }

          

int main()

{

           int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };

           vector< int, allocator > vec( ia, ia+12 );

                 

     // печатается: 51 35 40 23 29 20 26 22 19 12 17 15

           make_heap( &ia[0], &ia[12] );

     void (*pfi)( int ) = print_elements;

     for_each( ia, ia+12, pfi ); cout << "\n\n";

     // печатается: 12 17 15 19 23 20 26 51 22 29 35 40

     // минимальный хип: в корне наименьший элемент

           make_heap( vec.begin(), vec.end(), greater<int>() );

     for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

     // печатается: 12 15 17 19 20 22 23 26 29 35 40 51

           sort_heap( ia, ia+12 );

     for_each(  ia, ia+12, pfi ); cout << "\n\n";

           // добавим новый наименьший элемент

           vec.push_back( 8 );

     // печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20

           // новый наименьший элемент должен оказаться в корне

           push_heap( vec.begin(), vec.end(), greater<int>() );

     for_each(  vec.begin(), vec.end(), pfi ); cout << "\n\n";

     // печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8

           // наименьший элемент должен быть заменен на следующий по порядку

           pop_heap( vec.begin(), vec.end(), greater<int>() );

     for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

}



Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий