有代码和出错测试点数据。
我总是看不出我的代码逻辑错误在哪。已经逐行检查过了。不知道为什么和预期结果不同
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// data structure: heap
inline int _ls(int x)
{
return 2*x+1;
}
inline int _rs(int x)
{
return 2*x+2;
}
inline int _fa(int x)
{
return (x-1)/2;
}
class _heap // 小根堆
{
private:
vector<int> Heap;
public:
int size=0;
void push(int x)
{
Heap.push_back(x);
int p=size;
size++;
if(!p)
return;
while(Heap[_fa(p)]>Heap[p] and p>0)
{
swap(Heap[_fa(p)],Heap[p]);
p=_fa(p);
}
}
int top(void)
{
if(!size)
return 0;
return Heap[0];
}
void pop(void)
{
if(!size)return;
size--;
swap(Heap[size],Heap[0]);
int p=0,minp;
while(_ls(p)<size)
{
minp=(Heap[_ls(p)]<Heap[_rs(p)])?_ls(p):_rs(p);
if(_rs(p)==size)
minp=_ls(p);
if(Heap[p]>Heap[minp])
swap(Heap[p],Heap[minp]);
else
break;
p=minp;
}
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
_heap a;
int n,op,x;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>op;
if(op==1)
{
cin>>x;
a.push(x);
}
else if(op==2)
{
cout<<a.top()<<endl;
}
else
{
a.pop();
}
}
}
input
15
1 5384
2
3
1 4337
1 291
3
1 3776
2
1 2490
1 3903
1 5038
1 4504
3
3
3
output
5384
3776