siftup模板
当然还得有siftdown模板
“稍”加调试,就可以得到模板代码
#include<bits/stdc++.h> using namespace std; int n,op,sl=0,h[1000010]; void jh(int x,int y)//交换 { int z=h[x]; h[x]=h[y]; h[y]=z; } void siftu(int i)//siftup { bool f=true; while(f)//因为是小顶堆,所以必须考虑没有儿子的情况 { if(i==1 || h[i/2]<=h[i]) //当元素位于堆顶或正确位置时 f=false;//跳出循环 else { //元素比它的父亲小,因此交换 jh(i,i/2); i/=2; } } } void siftd(int i)//siftdown { bool f=true; while(f) { if(i*2+1<=sl) //当它有右儿子时 if(h[i]>h[i*2+1]) //它比右儿子大 if(h[i*2+1]>h[i*2]) { //右儿子比左儿子大,左儿子最小 jh(i,i*2); i*=2; }else { //否则交换右儿子 jh(i,i*2+1); i=i*2+1; } else if(h[i]>h[i*2]) { //右儿子比它大,但左儿子比它小 jh(i,i*2); i*=2; }else //两个儿子都比他小,到达正确位置 f=false; else if(i*2<=sl) //它没有右儿子,但有左儿子 if(h[i]>h[i*2]) { jh(i,i*2); i*=2; }else f=false; else //没有儿子(就很惨),位置一定正确 f=false; } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>op; if(op==1) { sl++;//堆的数量增加 cin>>h[sl];//在末尾输入 siftu(sl); }else if(op==2) cout<<h[1]<<endl; else if(op==3) { h[1]=h[sl];//将末位元素直接覆盖到堆顶 sl--;//数量减少 siftd(1); } } return 0; }
如果没看懂,很正常,再看一遍,或者再继续理解小顶堆的基本逻辑
如果看懂了上面的算法,事情就变得简单了,就可以理解并轻松使用c++提供的STL来完成
#include<bits/stdc++.h> using namespace std; int n,op,sr; int main() { priority_queue< int,vector<int>,greater<int> >h; //定义 cin>>n; for(int i=1;i<=n;i++) { cin>>op; if(op==1) { cin>>sr; h.push(sr); }else if(op==2) cout<<h.top()<<endl; else if(op==3) { h.pop(); } } return 0; }
标签:洛谷,int,else,jh,P3378,儿子,模板,op From: https://www.cnblogs.com/fc2110rxr/p/17538352.html