数组模拟手写一个堆

短命女 2021-06-22 15:37 454阅读 0赞

堆也就是c++stl容器中是priority_queue，
    但是不支持删除任意一个元素，所以手写一个堆和一些基本操作

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <map> 
    #include <queue>
    using namespace std;
    const int maxn=1e5+10;
    int n,m,cnt; 
    int heap[maxn];//注意堆的数组应该从下标为1开始存 
    void down(int u){ 
    	int t=u;//用来存放当前最小值的下标 
    	if(u*2<=cnt&&heap[u*2]<heap[t]){ //如果存在左孩子，并且左孩子比当前最小值小，就赋值给最小值 
    		 t=u*2;
    	}
    	if(u*2+1<=cnt&&heap[u*2+1]<heap[t]){ //如果存在右孩子，并且右孩子比当前最小值小，就赋值给最小值 
    		 t=u*2+1;
    	}
    	if(u!=t){ //如果最小值下标和开始下标不一样就交换 
    		swap(heap[u],heap[t]);
    		 down(t);//递归处理 
    	}
    }
    void up(int u){ 
    	while(u&&heap[u]<heap[u/2]){ //如果存在父节点，并且小于父节点的值就交换 
    		 swap(heap[u],heap[u/2]);
    		 u/=2;
    	}
    }
    
    int main(){ 
       cin>>n;
       cnt=n;//堆元素的个数 
       for(int i=1;i<=n;i++){ 
       	   cin>>heap[i];
       } 
       for(int i=n/2;i>=1;i--){ 
       	      down(i);
       }
       
       //操作1.求当前集合的最小值 
       cout<<heap[1]<<endl; 
       //操作2.插入一个数
       int x;
       cin>>x;
       heap[++cnt]=x; //在末尾加一个新的在up操作一遍 
       up(cnt);
        //操作3.删除最小值
    	heap[1]=heap[cnt];//用末尾的值覆盖第一个值 
    	cnt--;
    	down(1); 
       //操作4.删除任意元素
        int k;
    	cin>>k;//删除第k个元素
    	heap[k]=heap[cnt];
    	cnt--;
    	down(k); //up和down操作只会执行一个， 
    	up(k);
    	//操作5，修改任意元素
    	cin>>k>>x;//将第k个数修改为x 
    	 heap[k]=x;
    	 down(k);
    	 up(k);
    	 
       return 0;	
    }