为什么我的手写堆就是比别人慢??
查看原帖
为什么我的手写堆就是比别人慢??
376481
Carrot_Rui楼主2021/3/13 10:53

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;
}
                              
2021/3/13 10:53
加载中...