STL之heap学习

C++标准库中的堆-heap

make_heap函数，包括两个参数(begin(number),end(number)).（左闭右开）

pop_heap函数，包括两个参数，起始位置和终止位置，将当前区间的首位（也就是当前区间最大放在）end的位置。

push_heap函数，包括两个参数，起始位置和终止位置，将当前区间的最后一个元素插入到堆中。

sort_heap函数，包括两个参数，起始位置和终止位置，多次调用make_heap函数和pop_heap函数，实现最终对整个区间进行排序（注意调用之前需要先调用一次make_heap函数）。

is_heap函数，包括两个参数，起始位置和终止位置，判断当前的区间是否满足大顶堆，如果满足输出1，否则输出0。

is_heap_until函数，返回的是第一个不满足二叉堆的迭代器。

第一个参数代表起始位置，第二个参数代表结束位置。

每一次调用都是把当前区间内的最大值放在这个区间的最前面，就是堆排序的感觉。然后每排完一次序，我们可以将头部元素弹出。库函数 pop_head(begin(number),end(number)).这个时候，最大值被移动到了end的位置。

示例代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e5+100;
 6 int a[maxn];
 7 vector<int>q;
 8 int main(){
 9 for(int i=1;i<=5;i++){
10 q.push_back(i);
11 }
12 int n=0;
13 for(int i=1;i<=5;i++){
14 make_heap(q.begin(),q.begin()+q.size()-n);
15 for(int j=0;j<q.size();j++){
16 if(j==0)cout<<q[j];
17 else cout<<" "<<q[j];
18 }
19 cout<<endl;
20 pop_heap(q.begin(),q.begin()+q.size()-n);
21 n++;
22 }
23 return 0;
24 }

vector

sort_heap函数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e5+100;
 6 int a[maxn];
 7 vector<int>q;
 8 int main()
 9 {
10     for(int i=1; i<=10; i+=2)
11     {
12         q.push_back(i);
13     }
14    //   make_heap(q.begin(),q.begin()+q.size());
15       q.push_back(4);
16       make_heap(q.begin(),q.end());
17         for(int j=0; j<q.size(); j++)
18     {
19         if(j==0)
20             cout<<q[j];
21         else
22             cout<<" "<<q[j];
23     }
24     cout<<endl;
25       sort_heap(q.begin(),q.end());
26     for(int j=0; j<q.size(); j++)
27     {
28         if(j==0)
29             cout<<q[j];
30         else
31             cout<<" "<<q[j];
32     }
33     cout<<endl;
34 return 0;
35 }

View Code

is_heap函数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e5+100;
 6 int a[maxn];
 7 vector<int>q;
 8 int main()
 9 {
10     for(int i=1; i<=10; i+=2)
11     {
12         q.push_back(i);
13     }
14     for_each(q.begin(),q.end(),[](int i){cout<<" "<<i<<endl;});
15     //   make_heap(q.begin(),q.begin()+q.size());
16      q.push_back(4);
17       make_heap(q.begin(),q.end());
18       sort_heap(q.begin(),q.end());
19     int flag=is_heap(q.begin(),q.end());
20     cout<<flag<<endl;
21     return 0;
22 }

View Code

is_heap_until函数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e5+100;
 6 int a[maxn];
 7 vector<int>q;
 8 int main()
 9 {
10     for(int i=1; i<=10; i+=2)
11     {
12         q.push_back(i);
13     }
14     for_each(q.begin(),q.end(),[](int i){cout<<" "<<i<<endl;});
15     //   make_heap(q.begin(),q.begin()+q.size());
16      q.push_back(4);
17 //      make_heap(q.begin(),q.end());
18 //      sort_heap(q.begin(),q.end());
19     auto  flag=is_heap_until(q.begin(),q.end());
20     cout<<*flag<<endl;
21     return 0;
22 }

View Code

小总结：

pop_heap,push_heap,sort_heap函数都需要在make_heap函数的前提下使用。

C++标准库中的堆-heap

相关推荐