STL之heap学习
C++标准库中的堆-heap
make_heap函数，包括两个参数(begin(number),end(number)).（左闭右开）
pop_heap函数，包括两个参数，起始位置和终止位置，将当前区间的首位（也就是当前区间最大放在）end的位置。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。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函数的前提下使用。
更多精彩
