mycode:
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 9;
int n, m, h[N], sizee ;
inline void down(int t){
int u = t;
if(t<<1 <= sizee && h[t<<1] < h[u] ) u = t << 1;
if((t<<1)+1 <= sizee && h[(t<<1)+1] <= h[u]) u = (t << 1) + 1;
if(t != u){
swap(h[t],h[u]);
down(u); // 递归插入
}
}
inline void up(int t){
if(h[t>>1] > h[t]) swap(h[t>>1],h[t]),up(t>>1);
}
int main(){
cin>>n;
while(n--){
int op , x;
cin>>op;
if(op == 1) scanf("%d",&x), h[++ sizee] = x, up(sizee); //建堆
else if(op == 2) printf("%d\n",h[1]);
else if(op == 3) h[1] = h[sizee--], down(1); // 删除原根节点
}
return 0;
}
居然要2s 这是为什么(我吧*和/改成>> << 也没快多少)
别人的:
#include<bits/stdc++.h>
using namespace std;
int heap[10000000];
int hsize;
//插入函数,思路是将元素插入到最后的叶节点,然后往上跳,直到它的父节点小于它时
inline void _insert(int node,int num){
heap[node]=num;
if(heap[node>>1]>num){//判断父节点是否大于它(若大于,则交换
heap[node]=heap[node>>1];
_insert(node>>1,num);//交换父子位置
}
}
//删除函数
inline void _pop(int node,int num){
heap[node]=num;
if((node<<1)<=hsize&&(num>heap[node<<1]||num>heap[(node<<1)|1]))//如果它有子节点,且至少有一个小于它(及可进行交换)
{
heap[node]=heap[node<<1]<heap[(node<<1)|1]?heap[node<<1]:heap[(node<<1)|1];//让更小的与它交换,保证堆的稳定性
_pop(heap[node<<1]<heap[(node<<1)|1]?node<<1:(node<<1)|1,num);//判断应走哪一个子节点
}
}
int main()
{
int gs,cz,crs;
scanf("%d",&gs);
for(int zs=0;zs<gs;zs++){
scanf("%d",&cz);//三种操作
if(cz==1)scanf("%d",&crs),_insert(++hsize,crs);
if(cz==2)printf("%d\n",heap[1]);//堆顶即使最小值
if(cz==3)_pop(1,heap[hsize--]);//注意++、--的位置(我就在这里卡了好久/(ㄒoㄒ)/~~,30分的同学也有可能是在这里卡的)
}
return 0;
}
// STL #include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,a,b;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
if(a==1){
scanf("%d",&b);q.push(b);
}
else if(a==2) printf("%d\n",q.top());
else q.pop();
}
return 0;
}