Pagini recente » Cod sursa (job #2255802) | Cod sursa (job #1636360) | Cod sursa (job #1333335) | Cod sursa (job #290949) | Cod sursa (job #1512461)
#include <iostream>
#include <fstream>
using namespace std;
int H[200001],A[200001],Pos[200001],m,n,na;
void inserare(int x)
{
A[++na]=x;
H[++n]=x;
int fiu,tata;
fiu = n;
tata = n/2;
while(tata && H[tata]>x)
{
swap(Pos[H[tata]],Pos[H[fiu]]);
H[fiu]=H[tata];
fiu=tata;
tata=fiu/2;
}
H[fiu]=x;
Pos[fiu]=fiu;
}
void sterge(int x)
{
H[Pos[A[x]]]=H[n];
Pos[H[n]]=Pos[A[x]];
n--;
int fiu,tata,y;
y=H[n+1];
tata=Pos[A[x]];
fiu=tata/2;
while(fiu<=n)
{
if (fiu<n && H[fiu]>H[fiu+1]) fiu++;
if (y>H[fiu])
{
Pos[H[tata]]=Pos[H[fiu]];
H[tata]=H[fiu];
tata = fiu;
fiu=fiu*2;
}
else fiu=n+1;
}
Pos[y]=tata;
H[tata]=y;
}
void afisare()
{
for(int i=1;i<=n;i++)
cout<<H[i]<<" ";
cout<<endl;
for(int i=1;i<=na;i++)
cout<<A[i]<<" ";
cout<<endl;
for(int i=1;i<=na;i++)
cout<<Pos[i]<<" ";
cout<<endl;
}
int main()
{
ifstream f("heapuri.in");
ofstream g("heapuri.out");
f>>m;
int x,y;
for(int i=1;i<=m;i++)
{
f>>x;
if(x==1)
{
f>>y;
inserare(y);
}
else if(x==2)
{
f>>y;
sterge(y);
}
else g<<H[1]<<'\n';
if(x<3)cout<<x<<" : ",afisare();
}
f.close();
g.close();
return 0;
}