is_heap_until^C++11

[機能]

　　範囲がヒープ化されているか判定し，ヒープ化されていない最初の要素を指すイテレータを返します．ここで，ヒープとは，木構造の一種であり，親ノードの値が子ノードの値より常に大きい（または，小さい）という条件を満たしています．2 引数の比較関数を指定することも可能です（下の表現，sort 参照）．

[形式]

#include <algorithm>

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

[使用例]

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

   #include <stdio.h>
   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   using namespace std;
   
   int main()
   {
   					// 初期設定
   	vector<int> v1 {5, 10, 3, 4};
   	bool b = is_heap(v1.begin(), v1.end());
   	printf("初期状態 v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	cout << boolalpha << " ヒープ化？ : " << b << endl;
   					// v1 をヒープ化（make_heap）
   	printf("v1 をヒープ化（make_heap）\n");
   	make_heap(v1.begin(), v1.end());
   	b = is_heap(v1.begin(), v1.end());
   	printf("  make_heap v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	cout << " ヒープ化？ : " << b << endl;
   					// 要素を追加してヒープ化
   	printf("要素を追加してヒープ化（push_heap）\n");
   	v1.push_back(7);
   	b = is_heap(v1.begin(), v1.end());
   	printf("  7 を追加(push_back) v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	cout << " ヒープ化？（全体） : " << b << endl;
   	b = is_heap(v1.begin(), v1.end()-1);
   	cout << "    ヒープ化？（最初の 4 個） : " << b << endl;
   	vector<int>::iterator it = is_heap_until(v1.begin(), v1.end());
   	printf("    ヒープ化されていない要素 : %d\n", *it);
   
   	push_heap(v1.begin(), v1.end());
   	b = is_heap(v1.begin(), v1.end());
   	printf("  7 を追加(push_heap) v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	cout << " ヒープ化？（全体） : " << b << endl;
   					// 先頭と末尾を入れ替えてヒープ化(pop_heap)
   	printf("先頭と末尾を入れ替えてヒープ化（pop_heap）\n");
   	pop_heap(v1.begin(), v1.end());
   	printf("  先頭と末尾を入れ替えてヒープ化(pop_heap) v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	b = is_heap(v1.begin(), v1.end());
   	cout << " ヒープ化？（全体） : " << b << endl;
   	b = is_heap(v1.begin(), v1.end()-1);
   	cout << "    ヒープ化？（最初の 4 個） : " << b << endl;
   
   	v1.pop_back();
   	printf("  最後の要素を削除(pop_back) v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	b = is_heap(v1.begin(), v1.end());
   	cout << " ヒープ化？（全体） : " << b << endl;
   					// ヒープ化した範囲を並べ替える(sort)
   	printf("ヒープ化した範囲を並べ替える(sort_heap)\n");
   	sort_heap(v1.begin(), v1.end());
   	printf("  sort_heap v1:");
   	for (auto x : v1)
   		printf("  %d", x);
   	b = is_heap(v1.begin(), v1.end());
   	cout << " ヒープ化？（全体） : " << b << endl;
   
   	return 0;
   }
   			

   （出力）

   初期状態 v1:  5  10  3  4 ヒープ化？ : false
   v1 をヒープ化（make_heap）
     make_heap v1:  10  5  3  4 ヒープ化？ : true
   要素を追加してヒープ化（push_heap）
     7 を追加(push_back) v1:  10  5  3  4  7 ヒープ化？（全体） : false
       ヒープ化？（最初の 4 個） : true
       ヒープ化されていない要素 : 7
     7 を追加(push_heap) v1:  10  7  3  4  5 ヒープ化？（全体） : true
   先頭と末尾を入れ替えてヒープ化（pop_heap）
     先頭と末尾を入れ替えてヒープ化(pop_heap) v1:  7  5  3  4  10 ヒープ化？（全体） : false
       ヒープ化？（最初の 4 個） : true
     最後の要素を削除(pop_back) v1:  7  5  3  4 ヒープ化？（全体） : true
   ヒープ化した範囲を並べ替える(sort_heap)
     sort_heap v1:  3  4  5  7 ヒープ化？（全体） : false
   			

[参照]

sort， pop_heap， make_heap， sort_heap， is_heap， push_heap