Pagini recente » Cod sursa (job #584031) | Cod sursa (job #1408992) | Cod sursa (job #634240) | Cod sursa (job #2582277) | Cod sursa (job #794503)
Cod sursa(job #794503)
#include<fstream>
using namespace std;
ifstream in("heapuri.in");
ofstream out("heapuri.out");
const int NMAX=200001;
int heap[NMAX];
int poz[NMAX];
int elementdeIntrodus[NMAX];
int lungHeap , nrOperatii , tipOp , elementdeSters;
void schimba(int i,int j)
{
int aux;
aux=heap[i];
heap[i]=heap[j];
heap[j]=aux;
poz[heap[i]] = i;
poz[heap[j]] = j;
}
void urca(int pozitie)
{
if(pozitie==1)
return;
while(elementdeIntrodus[heap[pozitie]]<elementdeIntrodus[heap[pozitie/2]])
{
schimba(pozitie,pozitie/2);
pozitie=pozitie/2;
}
}
void coboara(int pozitie)
{
int fs=2*pozitie;
int fd=2*pozitie+1;
int bun=pozitie;
if(fs<=lungHeap && elementdeIntrodus[heap[bun]]>elementdeIntrodus[heap[fs]])
bun=fs;
if(fd<=lungHeap && elementdeIntrodus[heap[bun]]>elementdeIntrodus[heap[fd]])
bun=fd;
if(bun!=pozitie)
{
schimba(pozitie,bun);
coboara(pozitie);
}
}
void sterge(int pozitie)
{
heap[pozitie] = heap[lungHeap];
lungHeap--;
poz[heap[pozitie]] = pozitie;
urca(pozitie);
coboara(pozitie);
}
int main()
{
in>>nrOperatii;
int nrCitite=0;
for(int i=1;i<=nrOperatii;i++)
{
in>>tipOp;
if(tipOp==1)
{
in>>elementdeIntrodus[++nrCitite];
lungHeap++;
heap[lungHeap]=nrCitite;
poz[nrCitite]=lungHeap;
urca(lungHeap);
}
if(tipOp==2)
{
in>>elementdeSters;
sterge(poz[elementdeSters]);
}
if(tipOp==3)
{
out<<elementdeIntrodus[heap[1]]<<"\n";
}
}
return 0;
}