Mai intai trebuie sa te autentifici.
Cod sursa(job #1418751)
Utilizator | Data | 13 aprilie 2015 21:53:57 | |
---|---|---|---|
Problema | Heapuri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.62 kb |
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define rest 200002
ifstream in("heapuri.in");
ofstream out("heapuri.out");
int P[rest],H[rest],Ent[rest];
int leftson(int i)
{
return (2*i);
}
int rightson(int i)
{
return(2*i+1);
}
int father(int i)
{
return(i/2);
}
void insertHeap(int n,int nth)
{
P[nth] = n;
Ent[n] = nth;
int pos = n;
while( pos>1 && H[pos]<H[father(pos)] )
{
swap(P[Ent[pos]],P[Ent[father(pos)]]);
swap(Ent[pos],Ent[father(pos)]);
swap(H[pos],H[father(pos)]);
pos = father(pos);
}
}
void deleteHeap(int &n,int x)
{
int pos = P[x],posmin;
swap(P[x],P[Ent[n]]);
swap(Ent[pos],Ent[n]);
swap(H[pos],H[n]);
n--;
do
{
posmin = pos;
if( leftson(pos)<=n && H[leftson(pos)]<H[posmin])
posmin = leftson(pos);
if( rightson(pos)<=n && H[rightson(pos)]<H[posmin])
posmin = rightson(pos);
if(posmin == pos)
break;
else
{
swap(P[Ent[pos]],P[Ent[posmin]]);
swap(Ent[pos],Ent[posmin]);
swap(H[pos],H[posmin]);
pos = posmin;
}
}while(1);
}
int main()
{
int NrEle,n,ele,i,op,x;
ele = n = 0;
in >> NrEle;
for( i = 1 ; i <= NrEle ; i++)
{
in >> op;
switch(op)
{
case 1 : in >> x; ++ele; H[++n] = x; insertHeap(n,ele); break;
case 2 : in >> x; deleteHeap(n,x); break;
case 3 : out<<H[1]<<"\n"; break;
}
}
return 0;
}