C ++ STLのヒープ-make_heap（）、push_heap（）、pop_heap（）、sort_heap（）、is_heap、is_heap_until（）

このセクションでは、C++STLに存在するヒープデータ構造を確認します。これにより、ヒープへの入力が高速になり、数値を取得すると常に最大の数値になります。つまり、残りの数値の最大数が毎回ポップアウトされます。ヒープの他の要素は、実装に応じて配置されます。ヒープ操作は次のとおりです-

• make_heap（） −これにより、コンテナ内の範囲がヒープに変換されます。

• フロント（） −これは、最大数であるヒープの最初の要素を返します。

例

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Top element is : " << heap.front() << endl;
}

出力

Top element is : 53

• push_heap（） −これは、要素をヒープに挿入した後、ヒープを再ヒープ化するのに役立ちます。ヒープのサイズは1ずつ増加します。ヒープには、新しい要素が適切に配置されます。

• pop_heap（） −これは、ヒープの最大要素を削除した後、ヒープを再ヒープ化するのに役立ちます。ヒープのサイズは1ずつ減らされます。要素を削除した後、ヒープ要素はそれに応じて再編成されます。

例

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Top element is : " << heap.front() << endl;
   heap.push_back(60);
   push_heap(heap.begin(), heap.end());
   cout <<"Top element after insert : " << heap.front() << endl;
   pop_heap(heap.begin(), heap.end());
   heap.pop_back();
   cout <<"Top element after deletion : " << heap.front() << endl;
}

出力

Top element is : 53
Top element after insert : 60
Top element after deletion : 53

• sort_heap（）：これは、ヒープソート手法によってヒープ要素を昇順でソートします。

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Before Sort : ";
   for (const auto &i : heap) {
      cout << i << ' ';
   }
   sort_heap(heap.begin(), heap.end());
   cout <<"\nAfter Sort : ";
   for (const auto &i : heap) {
      cout << i << ' ';
   }
}

出力

Before Sort : 53 43 33 38 28
After Sort : 28 33 38 43 53

• is_heap（） −これは、コンテナがヒープであるかどうかを確認するために使用されます。ほとんどの実装では、逆にソートされたコンテナーはヒープとして扱われます。この関数は、これがヒープの場合はtrueヒープを返し、それ以外の場合はfalseを返します。

• is_heap_until（） −これは、コンテナがヒープになるまでの位置へのイテレータを見つけるために使用されます。

例

理解を深めるために、次の実装を見てみましょう-

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   vector<int>::iterator iter;
   is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
   cout << endl;
   cout < "Heapify" << endl;
   make_heap(heap.begin(), heap.end());
   is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
   cout << endl;
   vector<int>::iterator iter2 = is_heap_until(heap.begin(), heap.end());
   cout <<"The heap elements are : ";
   for (iter=heap.begin(); iter!=iter2; iter++)
      cout << *iter <<" ";
}

出力

The is not a heap
Heapify
The is a heap
The heap elements are : 53 43 33 38 28