Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
28.
Операции с пирамидами в STL
Алгоритм push_heap
Прототипы:
template<typename RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<typename RandomAccessIterator,typename Compare>
void push_heap(RandomAccessIterator first,
RandomAccessIterator last,Compare comp);
Если диапазон [first;last-1) представляет собой пирамиду push_heap переставляет элементы диапазона [first;last), делая из него пирамиду. Мы говорим, что элемент в позиции last-1 «внесен в пирамиду».
Обозначим через N размер диапазона [first;last). Временная сложность алгоритма push_heap – O(logN).
Алгоритм pop_heap
Прототипы:
template<typename RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<typename RandomAccessIterator,typename Compare>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last,Compare comp);
Если диапазон [first;last) представляет собой пирамиду, pop_heap обменивает значение в позиции first со значением в позиции last-1 и выполняет перестановку элементов в диапазоне [first;last-1), превращая его в пирамиду.
Временная сложность алгоритма pop_heap – O(logN).
Алгоритм make_heap
Прототипы:
template<typename RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<typename RandomAccessIterator,typename Compare>
void make_heap(RandomAccessIterator first,
RandomAccessIterator last,Compare comp);
Алгоритм make_heap переставляет элементы в диапазоне [first;last) , организуя их в пирамиду.
Время работы алгоритма make_heap – линейное, с выполнением не более 3N сравнений.
Алгоритм sort_heap
Прототипы:
template<typename RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<typename RandomAccessIterator,typename Compare>
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last,Compare comp);
Алгоритм sort_heap сортирует элементы пирамиды в диапазоне [first;last).
Время работы алгоритма sort_heap – O(NlogN), с выполнением не более NlogN сравнений.
Алгоритм partial_sort
Прототипы
template <typename RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template <typename RandomAccessIterator,typename Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
Итератор middle должен указывать в диапазон [first;last). Если M=middle-first, то алгоритм помещает в [first;middle) M элементов, которые находились бы там, если бы весь диапазон [first;last) был отсортирован. Порядок остальных элементов (находящихся в диапазоне [middle;last)) не определен.
Время вычисления partial_sort составляет O(Nlogk), где N=last-first, k=middle-first.
Если middle=last, то это обычный алгоритм пирамидальной сортировки со временем работы O(NlogN).
Рассмотрим пример программы, демонстрирующей использования обобщенных операций над пирамидами и алгоритма partial_sort
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
//функциональный класс
class comp{
public:
//критерий сравнения x и y
bool operator()(int x,int y)
{return x%10<y%10;}
};
int main()
{ const int n=20;
//создаем вектор целых чисел
//и заполняем его
vector<int> vec(n);
ostream_iterator<int> out(cout," ");
for(int i=0;i<n;++i)
vec[i]=i;
//случайным образом перемешиваем элементы вектора
random_shuffle(vec.begin(),vec.end());
cout<<"Before sort:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//сортировка vect по убыванию с помощью push_heap и pop_heap:
//создаем минимальную пирамиду
for(int i=2;i<=n;++i)
push_heap(vec.begin(),vec.begin()+i,greater<int>());
cout<<"Min heap:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//сортируем по убыванию
for(int i=n;i>=2;--i)
pop_heap(vec.begin(),vec.begin()+i,greater<int>());
cout<<"After sort:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl<<endl;
//случайным образом перемешиваем элементы вектора
random_shuffle(vec.begin(),vec.end());
cout<<"Before sort:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//Сортировка vect по возрастанию с помощью make_heap и //sort_heap:
//создание максимальной пирамиды
make_heap(vec.begin(),vec.end());
cout<<"Max heap:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//сортируем по возрастанию
sort_heap(vec.begin(),vec.end());
cout<<"After sort\n";
copy(vec.begin(),vec.end(),out);
cout<<endl<<endl;
cout<<"Algorithm partial_sort\n";
//случайным образом перемешиваем элементы вектора
random_shuffle(vec.begin(),vec.end());
cout<<"Before sort:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//После сортировки - пять значений с минимальными
//последними цифрами
partial_sort(vec.begin(),vec.begin()+5,vec.end(),comp());
cout<<"After sort\n";
copy(vec.begin(),vec.end(),out);
cout<<endl<<endl;
//случайным образом перемешиваем элементы вектора
random_shuffle(vec.begin(),vec.end());
cout<<"Before sort:\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
//сортируем vec по возрастанию с помощью пирамидальной //сортировки
partial_sort(vec.begin(),vec.end(),vec.end());
cout<<"After sort\n";
copy(vec.begin(),vec.end(),out);
cout<<endl;
}