Pagini recente » Cod sursa (job #109269) | Cod sursa (job #226605) | Cod sursa (job #88471) | Cod sursa (job #2699081) | Cod sursa (job #255289)
Cod sursa(job #255289)
#include<stdio.h>
#define infile "heapuri.in"
#define outfile "heapuri.out"
#define nmax (200*1000+1)
int i[nmax]; //i[j]-retine valoarea celui de-al j-lea element intrat in heap
int p[nmax]; //p[j]-retine pozitia din hip a elementului j
int h[nmax]; //min-heap-ul
int n; //numarul de elemente din heap
int o; //numarul de operatii
//adauga un element in heap
void add(int x, int n)
{
int f=n,t=f/2; //fiul si tatal:P
while(t&&h[t]>x) //cat timp tatal e mai mare decat elementul
{
h[f]=h[t]; p[h[f]]=f; //copiez tatal la fiu, si modific pozitia ;))
f=t; t=f/2;
}
h[f]=x; p[x]=f; //plasam elementul, si salvam pozitia lui din heap
}
//combina elementul de la pozitia k cu fii lui, a.i. heap-ul sa respecte conditiile de heap :P
void comb(int k, int n)
{
int x=h[k]; //salvam valoarea ce trebuie mutata corect ;))
int t=k,f=2*t; //tatal si fiul ;))
while(f<=n) //cat timp taal are copil ;))
{
if(f<n&&h[f]>h[f+1]) f++; //este mai mic cel de-al doilea copil al tatalui :P
if(h[f]<x) //daca tot mai trebuie urcati fii
{
h[t]=h[f]; p[h[t]]=t; //urc fiul peste tata;))
t=f; f=2*t; //tatal devine fiu....si refacem fiul tatalui
}
else f=n+1; //inseamna k am gasit locul unde trebuie pus x;))
}
h[t]=x; p[h[t]]=t; //plasam elemntul la pozitia corecta
}
//sterge elementul de la pozitia k din heap
void delete(int k, int n)
{
h[k]=h[n+1]; //copiem ultima valoare din heap...peste valoarea pe care trebuie sa o stergem
p[h[k]]=k; //ii modificam si pozitia :P
comb(k,n); //refacem heap-ul ;))
}
int main()
{
int t,x;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
scanf("%d\n",&o); //citim numarul de operatii pe care le vom face ;))
while(o--) //cat timp avem de facut operatii
{
scanf("%d",&t); //citim tipul operatiei ;))
if(t==1) //avem de inserat un element in heap
{
scanf("%d",&x); i[++i[0]]=x; //salvam ca am intrat pe x :P
add(x,++n); //adaugam elementul x in heap
}
else if(t==2) //trebuie sa stergem un element din heap ;))
{
scanf("%d",&x); //numarul de ordine din intrari al elementului ce trebuie sters ;))
delete(p[i[x]],--n); //stergem al x-lea element intrat din heap
}
else if(t==3) printf("%d\n",h[1]); //afisem cea mai mica valoare din heap
}
fclose(stdin);
fclose(stdout);
return 0;
}