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;
}