とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

std::push_heap, std::pop_heap, std::make_heap, std::sort_heap

STL―標準テンプレートライブラリによるC++プログラミング 第2版

// P114 ex05-27.cpp
#include<iostream>
#include<vector>
#include<algorithm>
template<typename Container>
void Print(const Container& c){
 using std::copy;
 using std::ostream_iterator;
 using std::cout;
 copy(c.begin(), c.end(), ostream_iterator<int>(cout, " "));
 cout << std::endl;
}
int main(){
 using std::cout;
 using std::endl;
 using std::vector;
 using std::random_shuffle;
 using std::copy;
 using std::ostream_iterator;
 using std::push_heap;
 using std::pop_heap;
 using std::random_shuffle;
 using std::make_heap;
 using std::sort_heap;
 cout << "Illustrating the generic heap operations." << endl;
 const int N = 15;
 vector<int> v(N);
 for(int i = 0; i < N; ++i)v[i] = i;

 cout << "random_shuffle -> push_heap -> pop_heap" << endl;
 random_shuffle(v.begin(), v.end());
 Print(v);
 for(int i = 2; i < N; ++i)
  push_heap(v.begin(), v.begin() + i);
 Print(v);
 for(int i = N; i >= 2; --i)
  pop_heap(v.begin(), v.begin() + i);
 Print(v);

 cout << "random_shuffle -> make_heap -> sort_heap" << endl;
 random_shuffle(v.begin(), v.end());
 Print(v);
 make_heap(v.begin(), v.end());
 Print(v);
 sort_heap(v.begin(), v.end());
 Print(v);
}

出力例:

Illustrating the generic heap operations.
random_shuffle -> push_heap -> pop_heap
12 1 9 2 0 11 7 3 4 6 8 5 14 13 10
14 8 13 3 6 11 12 1 2 0 4 5 9 7 10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
random_shuffle -> make_heap -> sort_heap
0 1 9 5 11 13 12 7 2 4 10 14 8 3 6
14 11 13 7 10 9 12 5 2 4 1 0 8 3 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14