ｍａｋｅ＿ｈｅａｐ

[機能]

　　ヒープを構築します．ヒープとは，系列の中の最大要素をルートとした木構造です．2 引数の比較関数を指定することも可能です（下の表現）．

[形式]

	#include <algorithm>
	#include <functional>

	template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last);
	template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
		

[使用例]

1. make_heap，push_heap，pop_heap，及び，sort_heap の使用方法です．この例では，2 つの方法を使用して系列をソートしています．なお，pop_heap を実行しても，コンテナ内から要素が削除されるわけではなく，系列の最後に移動し，ヒープから外れるだけであることに注意してください．

   #include <stdio.h>
   #include <vector>
   #include <algorithm>
   #include <functional>
   using namespace std;
   
   bool less_a(int a, int b)
   {
   	return (bool)((a < b) ? 1 : 0);
   };
   
   class less_b : public binary_function<int, int, bool>
   {
   	public:
   		result_type operator() (first_argument_type a, second_argument_type b)
   		{
   			return (result_type)((a < b) ? 1 : 0);
   		}
   };
   
   int main()
   {
   	vector<int> v1;
   	vector<int>::iterator it;
   					// push_heap と pop_heap によるソート
   	printf("**初期状態 v1**\n");
   	v1.push_back(5);
   	v1.push_back(10);
   	v1.push_back(3);
   	v1.push_back(4);
   	v1.push_back(7);
   	for (it = v1.begin(); it != v1.end(); it++)
   		printf("  %d", *it);
   	printf("\n");
   
   	printf("push_heap\n");
   	for (int i1 = 2; i1 < 5; i1++) {
   		push_heap(v1.begin(), v1.begin()+i1);
   		for (it = v1.begin(); it <= v1.begin()+i1; it++)
   			printf("  %d", *it);
   		printf("\n");
   	}
   
   	printf("pop_heap\n");
   	for (int i1 = 5; i1 >= 2; i1--) {
   		pop_heap(v1.begin(), v1.begin()+i1);
   		for (it = v1.begin(); it < v1.begin()+i1; it++)
   			printf("  %d", *it);
   		printf("\n");
   	}
   
   	printf("push_heap と pop_heap によるソート結果\n");
   	for (it = v1.begin(); it != v1.end(); it++)
   		printf("  %d", *it);
   	printf("\n");
   					// make_heap と sort_heap によるソート
   	printf("**初期状態 v1**\n");
   	random_shuffle(v1.begin(), v1.end());
   	for (it = v1.begin(); it != v1.end(); it++)
   		printf("  %d", *it);
   	printf("\n");
   
   	printf("make_heap\n");
   	make_heap(v1.begin(), v1.end());
   							// 以下の方法でも可能
   //	make_heap(v1.begin(), v1.end(), less_a);
   //	make_heap(v1.begin(), v1.end(), less_b());
   //	make_heap(v1.begin(), v1.end(), less<int>());
   	for (it = v1.begin(); it != v1.end(); it++)
   		printf("  %d", *it);
   	printf("\n");
   
   	printf("make_heap と sort_heap によるソート結果\n");
   	sort_heap(v1.begin(), v1.end());
   	for (it = v1.begin(); it != v1.end(); it++)
   		printf("  %d", *it);
   	printf("\n");
   
   	return 0;
   }
   
   （出力）
   
   **初期状態 v1**
     5  10  3  4  7
   push_heap
     10  5  3
     10  5  3  4
     10  5  3  4  7
   pop_heap
     7  5  3  4  10
     5  4  3  7
     4  3  5
     3  4
   push_heap と pop_heap によるソート結果
     3  4  5  7  10
   **初期状態 v1**
     10  4  7  5  3
   make_heap
     10  5  7  4  3
   make_heap と sort_heap によるソート結果
     3  4  5  7  10
   			

[参照]

sort， push_heap， pop_heap， sort_heap