堆 46

	h->data =new int[max+1];

这里是中括号才行!

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<climits>
using namespace std;
typedef struct Node{
	int *data;
	int size;
	int capacity;
}heap,*Heap;


int n;
Heap initheap(int max){
	Heap h;
	h=new Node();
	if(!h) return NULL;
	h->data =new int[max+1];
	if(!h->data ) return NULL;
    h->data[0]=INT_MIN;
	h->capacity =max;
	h->size =0;
	return h;
}

void printheap(Heap h){
	for(int i = 1; i < h->size; i++)
		cout << h->data[i] << ' ';
	cout << h->data[h->size] << endl;
}

bool isFull(Heap h){
	return h->capacity ==h->size ;
}
bool isEmpty(Heap h){
	return h->size ==0;
}
void up(int k,Heap h){
	int x=h->data[k];
	int i;
	for(i=k;i>=1;i=i/2){
		if(x<h->data[i/2]) h->data[i]=h->data[i/2];
		else break;
	} 
	h->data[i]=x;
}

void down(int k,Heap h){
	int x=h->data[k];
	int i,child;
	for(i=k;i*2<=h->size;i=child){
		child=i*2;
		if(child<h->size && h->data[child]>h->data[child+1]) child++;
		if(x>h->data[child]) h->data[i]=h->data[child];
		else break;
	} 
	h->data[i]=x;
}
//用bool,因为插入会失败,堆满 
bool insertheap(Heap h,int x){
	if(isFull(h)) return false;
	h->data [++h->size ]=x;
	up(h->size ,h);
	return true;
} 



//用bool ,因为删除会失败,堆空
bool removeheap(Heap h){
	if(isEmpty(h)) return false;
	h->data [1]=h->data [h->size--];
	down(1,h);
	return true;
} 

Heap createheap(int *a,int size,int max){
	Heap h=initheap(max);
	if(!h) return NULL;
	h->size =size;//后--因为initheap中有一个0的初始化
	for(int i=1;i<=size;i++){
		h->data[i]=a[i-1];
	}
	for(int i=size/2;i>=1;i--){
		down(i,h);
	}
	return h;
	
}




void test01(){
	Heap h;
	int k,x,y;
	cin>>n>>k;
	h=initheap(n);
	
	while(k--){
		cin>>x;
		if(x==1){
			cin>>y;
			insertheap(h,y);
		} 
		else if(x==-1) removeheap(h);
		printheap(h);
	}
	

	
}


void test02(){
	int m;cin>>m;
	int x;
	int a[1001];
	for(int i=0;i<m;i++){
		cin>>x;
	    a[i]=x;
	}
	Heap h=createheap(a,m,1001);
	printheap(h);
}


int main(){
	test01();
	test02();
	return 0;
} 

stl写起来好方便 头文件#include<algorithm>
最大堆/最小堆stl用法

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	int n,k,x,y;
	cin>>n>>k;
	
	vector<int> q; 
	while(k--){
		int flag=0;
		cin>>x;
		if(x==1){
			cin>>y;
			if(q.size() <n){
				q.push_back(y);
				push_heap(q.begin() ,q.end() ,greater<int>());
			}	 
			
		} 
		else{
			pop_heap(q.begin() ,q.end() ,greater<int>());
			q.pop_back() ;
		}
		for(int x:q){
			if(flag) cout<<" ";
			cout<<x;
			flag=1;
		}
		cout<<endl;
	}
	
	
	
	
	int flag=0;
	q.clear() ;
	cin>>k;
	while(k--){
		cin>>x;
		q.push_back(x); 
	}
	make_heap(q.begin() ,q.end() ,greater<int>());
	for(int x:q){
		if(flag) cout<<" ";
		cout<<x;
		flag=1;
	}	
	
	
	
	return 0;
}

然后想试试c++里面优先队列写来着,发现不可以,因为题目每次都要输出当前结果,输出的话,优先队列只能判空输出。优先队列只适用于最终结果。头文件#include<queue>
priority_queue

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
	int n,k,x,y;
	cin>>n>>k;
	priority_queue<int,vector<int>,greater<int>>q; 
	while(k--){
		cin>>x;
		if(x==1){
			cin>>y;
			if(q.size() <n)
				q.push(y);
		}
		else{
			q.pop();
		}
		
	}
	while(!q.empty()){
		cout<<q.top() ;
		q.pop() ;
	}
	
	
	
	return 0;
	
}
上一篇:【leetcode 回溯dfs C++】46. Permutations


下一篇:CV学习笔记(二十):数据集拼接生成